题目链接：http://dsalgo.openjudge.cn/graph/10/submit/

AC代码

#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

vector<int> nexts[100001];
stack<int> topo;
int prevs[100001];

int main() {
    int N, n, m, a, b;
    scanf("%d", &N);
    while (N--) {
        int result = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            nexts[i].clear();
            prevs[i] = 0;
        }
        while (m--) {
            scanf("%d%d", &a, &b);
            nexts[a].push_back(b);
            ++prevs[b];
        }
        for (int i = 1; i <= n; ++i)
            if (prevs[i] == 0)
                topo.push(i);
        while (!topo.empty()) {
            int x = topo.top();
            topo.pop(); 
            ++result;    //这个相当于做了排序，但是本题不需要排序结果
            for (int i:nexts[x]) {
                --prevs[i];
                if (!prevs[i]) topo.push(i);
            }
        }
        puts(result < n ? "Yes" : "No");
    }
}

解题思路

拓扑排序

对于一个有向无环图，可以对所有节点进行拓扑排序，可是对于有向有环图，会发生什么情况呢？

比如题干中的这张图中，C→E→G→D→C构成一个环

C、E、G、D这个点是永远不可能进入排序队列的。可以反证：

1. 假设C出现在了图的拓扑序列中，那么在排序过程中，一定存在某一步，C还没有进入队列中，但是它的所有前驱结点已经进入队列（这时才可以把C压入队列）
2. 那么D作为C的一个前驱结点，此时一定已进入队列
3. 从而D的所有前驱结点都已经进入队列，从而G也已经进入队列
4. 依此类推，G的前驱E已经进入队列，E的前驱C应该也……
5. 诶等等????，C不是还没进入队列呢嘛？
6. 矛盾！证毕.

一个有向图中只要出现了环，就可以利用上面的方法证明，这个环里的所有节点都排不了序。

这样一来，思路就清晰了许多：直接写拓扑排序，如果所有结点都排上了，说明没有环，否则肯定有！

---

拓扑排序中使用的排序队列，可以是栈、队列、优先队列，分别对应深度优先搜索、广度优先搜索和自定义优先级搜索三种模式，其中使用优先队列通常能得到唯一答案.