欧拉回路
发布时间
阅读量：
阅读量
研究欧拉回路的深度优先搜索（DFS）算法的基本思想：通过深度优先搜索遍历每一个节点，并探索该节点的所有相连边。如果该边已经被访问过则跳过；持续探索下去直至完成整个图的遍历过程。框架如下:
void dfs(int x)
{
for(顶点v的所有的边)
{
if(used[endge])
{
这条边用过了，continue;
}
used[endge]=true;//标记这条边
dfs(endge->to);//遍历这条边指向的顶点
load.add(to);//把这个点加入到路径记录当中，load里面就是路径的答案
}
}如图所示，在某个系统架构中，红色路径形成一个闭合回路，并由多个关键节点构成；而绿色部分则代表一个特定节点内的内部循环；在这样的情况下，则满足了完整的欧拉回路条件。
寻找欧拉回路的方法是观察深度优先搜索深入至最深处时的情况。当深度优先搜索深入至最深处时必然返回起点，并表明我们已经找到了一个红色环。然而，并非所有边都被访问过，在深度优先搜索返回时，在访问该绿色节点时如果还存在可探索的道路，则继续探索后必然返回该绿色起点。因此，在这种情况下将经历的所有边记录下来就形成了从终点到起点的一个完整的欧拉回路
#include<bits/stdc++.h>
#define sf(a) scanf("%d",&a)
using namespace std;
const int N=1e5+10,M=1e6;
int idx;
int e[M],nxt[M],h[N],out[N],in[N],ans[M];
bool use[M];
int n,m,type,cnt;
void dfs(int x)
{
for(int &i=h[x];~i;)//直接让i和h[x]的值一样，对于多个自环的情况可以避免超时
{
if(use[i])
{
h[x]=nxt[i];
continue;
}
use[i]=true;
if(type==1)
{
use[i^1]=true;
}
int t;
if(type==1)
{
t=i/2+1;
if(i%2==1)t=-t;
}
else t=i+1;
dfs(e[i]);
ans[++cnt]=t;
}
}
void add(int a,int b)
{
e[idx]=b,nxt[idx]=h[a],h[a]=idx++;
}
int main ()
{
memset(h,-1,sizeof(h));
sf(type),sf(n),sf(m);
for(int i=1;i<=m;i++)
{
int a,b;
sf(a),sf(b);
add(a,b);
if(type==1)
{
add(b,a);
}
out[a]++;
in[b]++;
}
if(type==1)
{
for(int i=1;i<=n;i++)
{
if((out[i]+in[i])&1){
puts("NO");
return 0;
}
}
}
else
{
for(int i=1;i<=n;i++)
{
if(out[i]!=in[i]){
puts("NO");
return 0;
}
}
}
for(int i=1;i<=n;i++)
{
if(h[i]!=-1)
{
dfs(i);
break;
}
}
if(cnt<m)
{
puts("NO");
return 0;
}
puts("YES");
while(cnt)
{
printf("%d ",ans[cnt]);
cnt--;
}
return 0;
}全部评论 (0)
还没有任何评论哟~