浅谈图论算法——图的连通性

浅谈图论算法——图的连通性

一, 图的连通性(Topsort)

Topsort是针对DAG(有向无环图)，检查其连通性的图论算法。

算法过程：统计所有节点的入度，如果当前节点的入度为0，则将当前节点入队，对于每个节点枚举他的所有出边，出点入度减减，重复此过程。
板子题：Topsort(模板)

[code]#includeusing namespace std;const int N = 1010;int e[N], ne[N], h[N], idx = 0;int n, din[N];inline void add (int a, int b) {    e[idx] = b;    ne[idx] = h[a];    h[a] = idx ++;}inline void Topsort() {    queue q;    for (int i = 1; i  x >> m; st[x] = 1;        for (int j = 1; j > y;            add (x, y); din[y] ++;        }    }    Topsort();    if (ans == n) puts("YES");    else cout > m >> s >> t >> t0;    for (int i = 1; i > a >> b >> c;        add (a, b, c); din ++;    }    cnt = 1;    Topsort();    cout  n >> m;    memset(h, -1, sizeof h);    for (int i = 1; i > a >> b;        add (a, b);    }    for (int i = 1; i  k;    for (int i = 1; i > v >> w;    memset(h, -1,  sizeof h);    for (int i = 1; i > a >> b;        add (a, b); add (b, a);    }    for (int i = 1; i