反过来调过去,我还是感觉没学明白缩点
接下来开始算法流程。
1. 树枝边: low_x= min(low_x,low_v) v 到达的点x一定可以到达,且v与x有祖宗关系
2. 后向边: low_x= min(low_x,low_v) v 的祖先一定是 x 的祖先
3. 横叉边:此时分两种情况考虑的
当 v 点已经退栈时,那么点v可到达的DFS序最小的祖先不是x的祖先,对 low_x 没有贡献; 当点v还在栈中时,v 点可到达的DFS序最小的祖先是x的祖先,有 low_x=min(low_x,low_v) (点v可到达的DFS序最小的祖先一定是x的,v 点能到达的点,x一定能到达) 特别地,由于前向边的更新对于求强连分量没有帮(更新是重复的),所以我们也可以有 low_x=min(low_x,low_v)
那么我们只需判断点 x 连出的边是哪一条就可以转移了。显然,当 dfn_v=0 时(此时v未被访问过),这是一条树枝边。我们再维护一个 col 数组, col_i 表示点 i 所在的强连通分量,在点 i 退栈时,我们对col进行赋值,那么当 dfn_v≠0&&col_v=0 时,点v一定在栈中(后向边指向的点一定在栈中,横叉边指向的点满足此条件时在栈中,而前向边是否存在与答案无关),此时用 low_x=min(low_x,low_v) 转移即可,否则无需转移。该算法时间复杂度为(n+m),因为深度优先遍历每个点只会经过一次,每条边也只会访问一次,而每个点都只会进/出栈一次,所以总时间复杂度为(n+m)
//把一个点当成根提溜出来,抖搂抖搂成一棵树 void dfs(int u) { //记录dfs序 //可通过任意多dfs边与最多一条非树返祖边到达的、本强连通分量内最小点 dfn[u]=low[u]=++dfs_clock; s.push(u); for(int v:g[u]) { if(!dfn[v])//树边 { dfs(v); low[u]=min(low[u],low[v]); } else if(!sccnum[v])//返祖 low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { scccnt++;//强连通块+1 while(1) { int x=s.top(); s.pop(); sccnum[x]=scccnt; sccsz[scccnt]++; if(x==u) break; } } }