割点
bool iscut[N]; int dfn[N], low[N], Index, n; void tarjan(int x) {///对于无向图,只要连通,就是强连通! ///判断割点呢,就是只要他所进入的强连通分量low全部满足<=dfn[自己]就可以了 dfn[x] = low[x] = ++Index;///时间戳和low for (int tmp = v[x], k; k = p[tmp].k, tmp; tmp = p[tmp].pre) if (!dfn[k]) { tarjan(k); if (dfn[x] <= low[k]) iscut[x] = true; low[x] = min(low[ x], low[k]); } else low[x] = min(low[x], dfn[k]); }///主要是因为是无向图,所以简单多了 ///唉,记得啊,这不是求强连通分量!只是看着像,借用low而已! ///因为low数组可以刻画dfs的一种遍历顺序,入口和出口的确定,而这正是确定割点所需要的. void cutpoint() { int num = 0; dfn[1] = Index = 1;///选择1这一点 for (int tmp = v[1], k; k = p[tmp].k, tmp; tmp = p[tmp].pre)///遍历这一点的每一条边 if (!dfn[k]) { num++;///有几个强连通分量 tarjan(k); } iscut[1] = num > 1;///如果这一点出发有多于一个强连通分量,则本身是割点 }
割边
///考虑重边 void tarjan(int x) { dfn[x] = low[x] = ++Index; for (int tmp = v[x], k; k = p[tmp].k, tmp > 1; tmp = p[tmp].pre) if (!p[tmp].used) {///遍历没有走过的边 p[tmp^1].used = p[tmp].used = true; ///将反向边同样标记(实际上的同一条边),而连接同两个点的重边则不会受影响 if (!dfn[k]) { tarjan(k); if (dfn[x] < low[k])///注意把反向边标记之后的效果,有重边就会相等,没有重边就会直接出栈退回 p[tmp].iscut = true; low[x] = min(low[x], low[k]); } else low[x] = min(low[x], dfn[k]); } } void cutline() { for (int i = 1; i <= n; i++)///恢复了任选一个点~ if (!dfn[i]) tarjan(i); }