浅谈图论算法——图的连通性
一, 图的连通性(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 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
