浅谈图论算法——图的连通性
浅谈图论算法——图的连通性一, 图的连通性(Topsort)
Topsort是针对DAG(有向无环图)，检查其连通性的图论算法。
算法过程：统计所有节点的入度，如果当前节点的入度为0，则将当前节点入队，对于每个节点枚举他的所有出边，出点入度减减，重复此过程。
板子题：Topsort(模板)
#includeusing namespace std;const int N = 1010;int e, ne, h, idx = 0;int n, din;inline void add (int a, int b) { e = b; ne = h; h = idx ++;}inline void Topsort() { queue q; for (int i = 1; ix >> m; st] = 1; for (int j = 1; j > y; add (x, y); din ++; } } 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(); coutn >> m; memset(h, -1, sizeof h); for (int i = 1; i > a >> b; add (a, b); } for (int i = 1; ik; 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
页:
[1]