[解题报告]ural 1176 Hyperchannels

Abstract

ural 1176

欧拉回路

Body

Source

http://acm.timus.ru/problem.aspx?space=1&num=1176

Description

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

Solution

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

消圈法的基本思路如下：

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

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

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

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int N, S;
vector<int> adj[1010];
vector<int> 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