posted on 2022-07-07 20:52:49 | under 模板 | source
0x00 有向图缩点
现有一有向图 \(G=(V,E)\)，称一个点集 \(E'\in E\) 为强连通分量，当且仅当 \(E'\) 的任意两点可以互相到达（围成一个环），求出所有极大强连通分量即 \(\tt SCC\)。
使用 Tarjan，我们将这个有向图看成一棵树，dfs 遍历，用 \(dfn_u\) 记录访问点 \(u\) 的时间戳。由于它是一个图，所以会有一些边返回到其它访问过的点（有可能是它的兄弟或者祖先，这不重要），称作返祖边。
记录 \(low_u\)，它表示点 \(u\) 通过 dfs 树和最多一次返祖边能到达的最小的 \(dfn\)。如果 \(low_u=dfn_u\)，我们断言点 \(u\) 的整一棵子树是一个 \(SCC\)，因为从点 \(u\) 出发能回到点 \(u\)，就是一个环。但是，\(low_u\) 不能经过已经缩完点的点，这样两个 \(SCC\) 就套在一起了，可以合成一个大的 \(SCC\) 了。
int dfn[1010],low[1010],stk[1010],col[1010],cnt,top,tot;
void reset(){
cnt=0;
tot=0;
memset(dfn,0,sizeof dfn);
memset(col,0,sizeof col);
}
void tarjan(int u){
low[stk[++top]=u]=dfn[u]=++cnt;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(!col[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
col[u]=++tot;
while(stk[top]!=u) col[stk[top--]]=tot;
top--;
}
}