对于一个有向图，可以通过拓扑排序（Topological Sort）来判断是否是有向无环图（Directed Acyclic Graph，DAG）。
我总结了一下拓扑排序的思想，下面来说一说。

拓扑排序的算法思想是：

  1. 每次从图中取出入度为 0 的节点
  2. 删除该节点发出的所有边，进行（1）步骤
    邻接表的实现方式如下：
    toposort
    初始的时候建立两个表，一个邻接表，以及另外一个表存储出度为0的节点，每次将入度表中入度为 0 的点加入容器中，然后从容器中取出节点，去邻接表中查询，根据邻接表修改入度表，发现入度为 0 的点加入容器中，如此反复，直至容器为空。
    如果最终入度表中有入度不为 0 的节点，则该图有环，否则该图无环。若该图为偏序关系，则某一时刻容器中的元素多于一个，取出的元素可能是随机的，造成拓扑排序的结果不唯一，与容器的选取有关。若该图为全序关系，则容器中的元素始终只有一个，结果唯一，与容器的选取无关。
    下面以题为例说明：
    HDU 3342
    题意：有一个 ACM 日常 QQ 交流群，群内存在一些师徒关系，若存在某个人的徒弟是自己的师傅的情况则不合法，输出 NO，否则输出 YES。此题有 trick，即要判断重边，代码如下
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <set>
    using namespace std;
    int main()
    {
        int n, m, x, y, cnt, table[105];
        bool vis[105][105];  //防止出现重边
        while(scanf("%d%d", &n, &m) && n && m)
        {
            cnt = 0;
            memset(vis, 0, sizeof(vis));
            memset(table, 0, sizeof(table));
            vector<int> v[105];  //邻接表
            set<int> st;  //存储入度为0的节点
            set<int>::iterator it;
            for(int i = 0; i < m; i++)
            {
                scanf("%d%d", &x, &y);
                if(!vis[x][y])
                {
                    v[x].push_back(y);
                    table[y]++;
                    vis[x][y] = true;
                }
            }
            for(int i = 0; i < n; i++)
                if(table[i] == 0)
                    cnt++, st.insert(i);
            while(!st.empty())
            {
                it = st.begin();
                for(unsigned int i = 0; i < v[*it].size(); i++)
                {
                    table[v[*it][i]]--;
                    if(table[v[*it][i]] == 0)
                        cnt++, st.insert(v[*it][i]);
                }
                st.erase(*it);
            }
            printf(cnt == n ? "YES\n" : "NO\n");
        }
        return 0;
    }
文档信息
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
本文链接：www.snovey.com/2016/06/toposort.html