tarjan算法中关于连通分量的整理

主要涉及的问题
1、缩点 –强连通块
2、连通块 – 桥 – 割点

有向图的强连通分量

对于一个有向图，连通分量：对于分量中任意两点u, v，必然可以从u走到v，且从v走到u。
强连通分量：极大连通分量

模板： 求强连通分量
缩完点以后是一个拓扑图（且dfs逆序即scc_cnt逆序就是拓扑序）

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[j]);
    }
    if(dfn[u] == low[u])
    {
        int y;
        scc_cnt++;
        do{
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            scc_size[scc_cnt]++;
        }while(y != u);
    }
}

无向图的强连通分量

1 边的双连通分量 e-dcc 极大的不包含桥的连通块
2 点的双连通分量 v-dcc 极大的不包含割点的连通块

/*
桥  
 o-o 桥o-o
 | | ↓ | |
 o-o - o-o 
1 如何找桥？ x
            /
           y
x和y之间是桥 <=> dfn[x] < low[y] y无论如何往上走不到x 
                +y能到的最高的点low[y] = dfn[y]
2 如何找所有边的双连通分量？
2.1 将所有桥删掉
2.2 stack
dfn[x] == low[x] 
<=> x无论如何走不到x的上面
<=> 从x开始的子树可以用一个栈存

每个割点至少属于两个连通分量

*/

模板： 求边双连通分量
缩完以后是一棵桥都保留着的树

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])  // j未遍历过
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if (dfn[u] < low[j])  // j到不了u
                is_bridge[i] = is_bridge[i ^ 1] = true;  // 正反向边都是桥
        }
        else if (i != (from ^ 1)) // j遍历过 且i不是反向边
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ dcc_cnt;
        int y;
        do {
            y = stk[top -- ];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

/*
3 割点
    割点 
 o-o   o-o
 |  \↓/  |
 o-o-o-o-o 
3.1求割点
     x   
     |
     y
要求low[y] > dfn[x] y能到达的最早的节点>x的时间戳
否则low[y] ≤ dfn[x]时,即y能到比xdfs序小的点,则存在环
    →o
   | ↓    
   | x   
   | |
   o←y
low[y]≤dfn[x]的情况下
1 如果x不是根节点 那么x是割点
2 x是根节点 至少有两个子节点yi 
            且有low[yi]≥dfn[x]
            如果只有一个子结点 去完根节点x
            x   
            |   →   y1  子节点部分还是连通的
            y1
            如果有两个子结点 去完根节点x
            x  
           / \  →   y1  y2 之间不连通
          y1 y2 
3.2 求点双连通分量
     o x
     |
     o y
stk[]
if(dfn(x)<=low(y))
{
    cnt++
    if(x非根||cnt>1)x是割点
    stk.pop(j) while j!=y将栈中元素弹出至y为止
    且x也属于该 点双连通分量
}
*/

模板： 求割点数量
求的是连通块内割点的数量

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;

    int cnt = 0;
    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]);
            if (low[j] >= dfn[u]) cnt ++ ;
        }
        else low[u] = min(low[u], dfn[j]);
    }

    if (u != root) cnt ++ ;

    ans = max(ans, cnt);
}

模板： 求点双连通分量
求完以后vector[HTML_REMOVED] dcc中是每个连通块中的点 且cut数组标记每个割点

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;

    if (u == root && h[u] == -1)
    {
        dcc_cnt ++ ;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0;
    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]);
            if (dfn[u] <= low[j])
            {
                cnt ++ ;
                if (u != root || cnt > 1) cut[u] = true;
                ++ dcc_cnt;
                int y;
                do {
                    y = stk[top -- ];
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
}