联通分量总结

有向图的强联通分量

• 将有向图中的边分为树枝边，前向边，后向边，横叉边
• 强联通分量的理解就是，强联通分量中的任意点都是可以相互到达的
• 使用有向图的强联通分量可以进行缩点，将原来的有向图转换成一个有向无环图（拓扑图），并可以采用倒序的方式进行拓扑顺序遍历
• tarjan算法，引入时间戳，根据dfs遍历的顺序，判断每个点遍历的时间和子树遍历到的最小时间来判断是否在同一强联通分量
• 并引入栈来将其枚举
• 如何讲一个缩点后的拓扑图通过加边变成强联通分量，只需要将入度为0的点记为din, 出度为0的点记作dout, 将哪个大的向小的连边，直到全部连满， 所以要填max(din, dout)条边

模板

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 t;
        ++ scc_cnt;
        do {
            t = stk[top --];
            in_stk[t] = false;
            id[t] = scc_cnt;
        }while (u != t);
    }
}

无向图的边双联通分量

• 引入桥的概念，如果将桥删除掉，整个图会变得不联通，那么这条边就称为桥
• 而边双联通分量就是没有桥的极大的连通块，任意一条路径没有公共边
• 如何找到桥
  首先桥是边is_bridge[M], 要遍历边
  如果x <=> y是桥
  说明 dfn[x] > low[y], 说明y无路如何都走不到x，说明(x, y)这条边断掉就分成了两个来联通分量
• 如何找到所有边联通分量
  • 方法1，将所有桥删掉，再有flood算法求所有联通分量即可
  • 方法2，使用栈，将所有边双联通分量加入
• 如何将一个树添加边，变成一个边双联通分量，只需要将叶子节点两两连边使其联通即可，将叶子节点个数即为cnt，需要连(cnt + 1) / 2条边
  模板

void tarjan(int u, int fb) // fb为到这个节点的边
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u;

    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){
            tarjan(j, i);//传入的是边
            low[u] = min(low[u], low[j]);

            if (dfn[u] < low[j])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if (i != (fb ^ 1))
            low[u] = min(low[u], dfn[j]);
    }

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

无向图的点双联通分量

• 引入割点的概念，如果将某个点与其所联通的边都删掉，那么这张图不联通了，那么这个点就被成为割点
• 而点双联通分量就是没有割点的极大的连通块

• 而如果一个无向图中存在割点，那么每个割点一定属于两个点双联通分量

• 如何求割点
  首先要满足x是割点，就必须有dfn[x] <= low[y]
  其次需要判断x是否为根节点
  $$ \begin{cases} x不是根节点，那x就是割点 \\ \\ x是根节点，则需要x至少有两个子节点（两个dfn[x_i] \leq low[y_i]） \end{cases} $$

• 如何求点双联通分量
  由于需要知道有多少个$dfn[x_i] \leq low[y_i]$, 所以使用一个变量cnt来保存
  因此要求出所有点联通分量就需要

if (dfn[x] <= low[y]){
    cnt ++;
    if (x != root || cnt > 1) cut[x] = true;
    //将栈中的元素弹出，直到弹出t为止
    //同时割点也在这个点双联通分量中
    //由于割点在多个点双联通分量中，所以使用vector存每个点双联通分量
}

需要特判孤立的点也是双联通分量
- 缩点方式
$$ \begin{cases} 每个割点单独作为一个点 \\ \\ 从V-DCC项其所包含的每个割点连一条边 \end{cases} $$
模板

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

    if (u == root && h[u] == -1){ //当u是孤立的点时，u也是点双联通分量
        ++ dcc_cnt;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt = 0; //统计有多少条 dfn[x] <= low[y], 用来判断是否是割点
    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]){ //此时u下面的就是点双联通分量
                cnt ++;
                if (u != root || cnt > 1) cut[u] = true; //判断u是否为割点，不是割点也能加入点双联通分量
                ++ dcc_cnt;
                int t;
                do {
                    t = stk[top --];
                    dcc[dcc_cnt].push_back(t);
                } while(t != j); //循环到j即可，易错
                dcc[dcc_cnt].push_back(u);//同时要将x加入到点双联通分量
            }
        }
        else low[u] = min(low[u], dfn[j]); //易漏，建议先写
    }
}