贪吃蛇地图：判断是否会吃到自己

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

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

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

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

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

输入格式

第一行为一个数：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，没有自环，允许重边

算法

(拓扑排序，DFS) $O(n+m)$

由于蛇头不能走回去，因此我们可以建立一个逆邻接表，然后按照拓扑排序的方式遍历，看是否存在环即可。

时间复杂度分析：每条边只会被遍历一次，因此时间复杂度为 $O(m)$。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 20000 + 5;
vector<int> G[MAXN]; // 逆邻接表
int in_degree[MAXN]; // 入度
bool vis[MAXN]; // 标记是否被访问过

bool dfs(int u) {
    vis[u] = true;
    for (int v : G[u]) {
        if (!vis[v]) {
            if (dfs(v)) return true;
        } else {
            return true; // 存在环路
        }  
    }
    return false; // 没有环路
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            in_degree[i] = 0;
            vis[i] = false;
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            G[y].push_back(x); // 建立逆邻接表
            in_degree[x]++; // 更新入度
        }
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }
        bool flag = false; // 标记是否存在环路
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (dfs(u)) { // 存在环路
                flag = true;
                break;
            }
            for (int v : G[u]) {
                if (--in_degree[v] == 0) {
                    q.push(v);
                }
            }
        }
        if (flag) {
            cout << 'No' << endl;
        } else {
            cout << 'Yes' << endl;
        }
    }
    return 0;
}