贪吃蛇游戏：判断是否存在欧拉回路

哲哲迷上了一个非常有意思的游戏，这个游戏的内容就是通过上下左右来操作一条蛇的前进，比方说，你现在正在向上走，而你按了一下右，那么这条蛇就会转向右走，很有趣吧！

这个游戏的名字叫做贪吃蛇。但是，这个看起来简单的游戏也挺需要操作的，如果你不小心撞到了墙，或是撞到自己的身体的话，你就输了。

可是，哲哲由于手指灵活度不够，经常撞墙而死，所以，他自己设计了一个没有墙的贪吃蛇地图，地图可以表示成若干个点，而你可以操作蛇头从某一个一个点到它相邻的点上。

这样，游戏的难度降低了许多，可是哲哲还是有可能挂掉的，因为他可能一不小心吃到自己。

现在，你得到了一些哲哲设计好的地图，哲哲希望你帮他看看他有没有可能一不小心碰到到自己的身体而导致游戏失败，为了简便，这里我们假设哲哲的蛇已经非常长了，长度可以视为无穷大。哲哲可以选任意点作为起点。

输入格式

第一行为一个数：t，表示哲哲设计好了 t 个地图

对于接下来的每一个地图，开头的为两个数：n，m，表示图中有 n 个点，编号为 1~n， m 条有向边

接下来 m 行，每行两个数 x，y，表示哲哲可以将蛇从 x 点移动到 y 点

输出格式

对于每个地图，输出 Yes 或 No，Yes 表示哲哲不可能吃到自己，No 表示哲哲有吃到自己的危险

输入输出样例

输入 #1

输出 #1

Yes
No

说明/提示

n<=20000，m<=100000，t<=20，没有自环，允许重边

算法

(图的遍历,拓扑排序) $O(n+m)$

题目分析

模拟贪吃蛇游戏，问题可以转化为，能否从任意一个点出发，经过若干条边最后回到这个点，而不重复经过任何一条边。

根据贪吃蛇的游戏规则，当蛇头从一个点移动到其它点时，除蛇头之外任何一个点都只能进入一次，因此问题转化为，可以从任意一个点出发，经过若干条边是否可以实现每条边仅经过一次，即图是否存在欧拉回路。

由于图可能存在多个连通块，因此需要对每个连通块分别进行判断是否存在欧拉回路。

判断欧拉回路的方法

判断欧拉回路的方法有很多种，这里给出两种：

DFS + 回溯，每次从一个点出发遍历到其它点，当所有的边都被遍历到时，判断是否回到了起点，如果回到了起点，则存在欧拉回路，否则不存在。
拓扑排序，如果存在欧拉回路，则图中所有点的入度和出度都是相等的。因此可以通过拓扑排序得到每个点的入度和出度，如果所有点的入度和出度都是相等的，则存在欧拉回路，否则不存在。

时间复杂度

使用拓扑排序，时间复杂度为 $O(n+m)$。

参考文献

算法竞赛进阶指南，刘汝佳著，第 6.2 章。

C++ 代码

方法一：DFS

// 方法一：DFS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 20000 + 5;
vector<int> G[MAXN];
int vis[MAXN];
int n, m;

bool dfs(int u, int cnt) {
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            if (dfs(v, cnt + 1)) {
                return true;
            }
        }
    }
    if (cnt == m && u == 1) {
        return true;
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            vis[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            G[x].push_back(y);
        }
        bool flag = false;
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                if (dfs(i, 1)) {
                    flag = true;
                    break;
                }
            }
        }
        if (flag) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

方法二：拓扑排序

// 方法二：拓扑排序
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 20000 + 5;
vector<int> G[MAXN];
int indegree[MAXN];
int n, m;

bool check() {
    for (int i = 1; i <= n; i++) {
        if (indegree[i] != G[i].size()) {
            return false;
        }
    }
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            indegree[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            G[x].push_back(y);
            indegree[y]++;
        }
        if (check()) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}