Abstract

ural 1176

欧拉回路

 

Body

Source

Description

给定一张有向图，求其欧拉回路。

Solution

因为老是忘了消圈法怎么写，这里记录一下。

消圈法的基本思路如下：

一张有向连通图的欧拉回路（假设存在）可以分解为若干个环。从起点（注意若欧拉回路存在，起点可以是任意的）开始，随意走一条路径，一定可以回到起点本身，亦即该路径一定是一个环。从原图中去掉该环。若路径经过的点中还有点连接着未被消去的边，则以该点为起点一定还能找到另一个环，将新找到的环从图中去掉并嵌入原来的环中。不断递归该过程，即可找到图的欧拉回路。

具体实现时，DFS+回溯即可。对于DFS到的当前点，随便找一条出边删去并DFS出边所指的点。若当前点已没有出边，说明以当前点为起点的环已经全部消去，将当前点加入答案序列的末尾。最终得到的答案序列为DFS序的逆序，可以根据需要反序。

伪代码很简单，直接看代码好了。

Code

#include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; int N, S; vector
         
           adj[1010]; vector
          
            path; void dfs(int u) { while (adj[u].size()) { int v = adj[u].back(); adj[u].pop_back(); dfs(v); } path.push_back(u); } int main() { int u, v, d; scanf("%d%d", &N, &S); for (u = 1; u <= N; ++u) for (v = 1; v <= N; ++v) { scanf("%d", &d); if (u!=v && d==0) adj[u].push_back(v); } dfs(S); reverse(path.begin(), path.end()); for (int i = 0; i < path.size()-1; ++i) printf("%d %d\n", path[i], path[i+1]); return 0; }
          
         
        
       
      
     

Reference