[Acwing] 有向图 强连通分量

定义

连通分量 : 对于分量(一个子图)中任意两点U,V 必然可以从U走到V,并且可以从V走到U

强连通分量 : 极大连通分量

作用 : 将任意一个 有向图 --缩点–> 有向无环图(DAG 拓扑图)

Dfs : 1.树枝边 : (X,Y) 点和点的边 2. 前向边 : (X,Y) X是Y的祖先节点 (3,6) 3. 后向边 : (X,Y) (7,1) 回搜的边 4. 横叉边 : (X.Y) 连向左边(已经被搜)的边

Tarjan

时间戳 : (就是每个点的访问次序)

对于每个点定义两个时间戳 : dfn[u] : 遍历到u的时间戳 low[u]: 从u开始走,所能遍历到的最小的时间戳是什么

如果u是其所在强连通分量的最高点,dfn[u] = low[u]

Tarjan过程

#include 
using namespace std;
const int N  = 10;
void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    
    stk[++top] = u ;
    in_stk[u] = true;
    
    for(int i = h[u];i;i=ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] =min(low[u],low[j]);
        }else if(in_stk[j])
            low[u] =min(low[u],dfn[u]);
    }
    if(dfn[u] == low[u])
    {
        int y;
        ++scc_cnt;
        
        do{
            y = stk[top--];
            in_stk[y] =false;
            id[y] = scc_cnt;
        }while(y!=u);
    }
}
void solve()
{
    
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

缩点

• 遍历所有点
• 遍历 i 的所有临点 j
• 如果 i和 j 不在 同一个scc当中的话 加一条新边 id(i) -->id(j)