判断有向图是否有环

方法一：拓扑排序

时间复杂度O(n^2)

比较常用的是用拓扑排序来判断有向图中是否存在环。

• 什么是拓扑排序呢？
  我们先定义一条u到v的边e=<u,v>,u<v;满足这样要求的序列称为拓扑序列，即前面节点小于后面节点。所以，拓扑序列可以有很多条。
  生成拓扑序列的算法就叫拓扑排序啦~
• 算法流程描述
  while(节点个数次（N）循环）
  1.找出入度为0的节点u（节点个数次（N）循环）
  2.删去这个节点u和从这个节点出发相连的边（<u,v1>,<u,v2>....,<u,vn>），更新这些边连的点（v1,v2,v3....vn）的入度信息。
  3.直到找不到入度为0的点（要是图里节点删完了（循环了N次）就是没环，还剩节点就有环）。
• 代码

#include<iostream>
#include<vector>
using namespace std;
#define MAXN 1000
 
int n, m;
vector<int> G[MAXN];
vector<int> topo;//存拓扑排序的序列
void read_graph()
{
    cin >> n >> m;;
    int u, v;//不带边权的图
    for (int e = 0; e < m; e++) {//有多少条边
        cin >> u >> v;
        G[u].push_back(v);//有向图
    }
}

bool topoSort()
{
    int indgree[MAXN] = { 0 };//入度信息
    int visit[MAXN] = { 0 };
    for (int i = 0; i < n; i++) {//初始化入度信息
        for (int j = 0; j < G[i].size(); j++) {
            indgree[G[i][j]]++;
        }
    }
    int control=0;
    while (control < n) {
        int u = 0,i;
        //找到入度为0的点
        for (i=0; i < n; i++) {
            if (!visit[i] && indgree[i] == 0) {
                u = i;
                break;
            }
        }
        if (i == n) {//找不到入度为0的点退出循环
            return false;
        }
        visit[u] = 1;//标记访问过
        topo.push_back(u);
        for (int j = 0; j < G[u].size(); j++) {//更新入度信息
            indgree[G[u][j]]--;
        }
        control++;
    }
    return true;//control=n 说明n个点都存入拓扑排序里，是无环的
}
int main()
{
    read_graph();
    for (int i = 0; i < n; i++) {
        cout << i<<":";
        for (int j = 0; j < G[i].size(); j++) {
            cout << G[i][j] << " ";
        }
        cout << endl;
    }
    if (topoSort()) {
        for (int i = 0; i < topo.size(); i++) {
            cout << topo[i] << " ";
        }
    }
    else {
        cout << "there exist circle" << endl;
    }
}

上面这个复杂度要O(n^2)

---

看到用栈可以简化到O(n+e); //链接
其实就是在找入度为0点的步骤那里做优化:
把入度为0的点入栈；
当栈不为空时，更新栈顶节点连接顶点的入度信息，如果为0入栈
_{个人理解：和BFS的模板格式有点像，一层一层的搜索，这里用栈替代了上面代码的visit数组，因为只对栈里的元素做操作，自然是未访问过的}

DFS

时间复杂度O(V+E)

link:detect cycle in a graph

用两个bool数组_visited[]和_recStack[]来记录对节点 的访问和入栈

- isCyclicUnit(int v) ----以v起点是否有环
- isCycle(int n) ----遍历n 个节点，调用isCyclicUnit(i)