int dfn[N], low[N], dfncnt, s[N], tp;int scc[N], sc; // 结点 i 所在 scc 的编号int sz[N]; // 强连通 i 的大小void tarjan(int u) { low[u] = dfn[u] = ++dfncnt, s[++tp] = u; for(int i = h[u]; i; i = e[i].nex) { const int &v = e[i].t; if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if(!scc[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]) { ++sc; while(s[tp] != u) scc[s[tp]] = sc, sz[sc]++, --tp; scc[s[tp]] = sc, sz[sc]++, --tp; }}
割点:
对于根节点,判断是不是割点很简单——计算其子树数量,如果有2棵即以上的子树,就是割点。因为如果去掉这个点,这两棵子树就不能互相到达。 对于非根节点,判断是不是割点就有些麻烦了。我们维护两个数组dfn[]和low[],dfn[u]表示顶点u第几个被(首次)访问,low[u]表示顶点u及其子树中的点,通过回边,能够回溯到的最早的点(dfn最小)的dfn值(但不能通过连接u与其父节点的边)。对于边(u, v),如果low[v]>=dfn[u],此时u就是割点。假设当前顶点为u,则默认low[u]=dfn[u],即最早只能回溯到自身。
有一条边(u, v),如果v未访问过,继续DFS,DFS完之后,low[u]=min(low[u], low[v]); 如果v访问过(且u不是v的父亲),就不需要继续DFS了,一定有dfn[v]<dfn[u],low[u]=min(low[u], dfn[v])。下面这个u==fa的意思是u==ROOT,他就喜欢传个fa
void tarjan (int u,int fa){ DFN[u]=LOW[u]=++idx; int child=0; for (int i=head[u];i!=0;i=pre[i].mark) { int nx=pre[i].nxt; if (!DFN[nx]) { tarjan (nx,fa); LOW[u]=min (LOW[u],LOW[nx]); if (LOW[nx]>=DFN[u]&&u!=fa) cut[u]=1; if(u==fa) child++; } LOW[u]=min (LOW[u],DFN[nx]); } if (child>=2&&u==fa) cut[u]=1;} for (int i=1;i<=n;i++) if (DFN[i]==0) tarjan (i,i); for (int i=1;i<=n;i++) if (cut[i]) tot++;
割边:
和割点差不多,还叫做割桥。
对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。 实现 和割点差不多,只要改一处:low(v)>dfn(u)就可以了,而且不需要考虑根节点的问题。割边是和是不是根节点没关系的,原来我们求割点的时候是指点v是不可能不经过父节点u为回到祖先节点(包括父节点),所以顶点u是割点。如果low(v)==dfn(u)表示还可以回到父节点,如果顶点v不能回到祖先也没有另外一条回到父亲的路,那么(u,v)这条边就是割边。