无向图的双连通分量(DCC)

可分为 边双连通分量(e-DCC) 与 点双连通分量(v-DCC)

注意：

  • 点双连通分量不一定是边双连通分量，边双连通分量也不一定是点双连通分量
  • 割点与桥没有什么本质的关系
  • 两个割点之间的边不一定是桥
  • 一个桥的两个端点不一定是割点

边双连通分量(e-DCC)

介绍

  • 桥：一条无向边，若删除此边，整个图变得不连通，则称这条边为“桥”。
  • 边双连通分量：极大的不包含“桥”的连通块，则称为“边的双连通分量”
  • 性质：
    1. 无论删除哪一条边，整个图一定还是连通的
    2. 任意两点之间一定包含两条不相交的路径(边不相交)。

Tarjan算法求边的双连通分量

  • 时间戳(timestamp)，dfn[N], low[N], 和有向图的强连通分量作用相同
  • 如何找到桥？
    • 若子节点可以走到父节点或祖先节点，则从父节点到子节点的边不是桥，等价于，若边 x-y 为桥，则 dfn[x] < low[y]
  • 如何找到边双连通分量？
    • 方法一：将所有桥删去
    • 方法二：类似于有向图的强连通分量的Tarjan算法，用栈(stk数组)维护，刚开始搜索加到栈里，若dfs[i] == low[i]的话(即、i的父节点到i这条边为桥)，则i当前所在的子树中的节点即为当前边的双连通分量中的点。

例题：395. 冗余路径

题意：

给定一个无向连通图，
问：最少加几条边，使得任何两点之间都至少有两条边；等价于，最少加几条边，可以将其变成边双连通分量。

结论1：

任何两点之间都至少有两条边；等价于，此图为边双连通分量

证明1：

  • 充分性：左 -> 右
    • 如果 任何两点之间都至少有两条边 则 此图是边双连通分量
    • 反证法：假设任何两点之间都包含两条互不相交的路径，如果其不是边的双连通分量，则意味着这个图中，至少存在一个桥。
    • 在桥两侧的连通块中任意找两个点x, y，则x到y的所有路径都经过桥这条边，所以x, y两点之间不存在两条互不相交的路径，与条件中的 任何两点直接按都包含两条互不相交的路径相矛盾，则假设不成立，原命题成立。
  • 必要性：左 <- 右
    • 如果 此图是边双连通分量 则 任何两点之间都至少有两条边
    • 左可推：此图不含桥，假设两点 x, y 则 x, y 的最短路径为连接 x, y 的一条边，对于该边中的每一段边，都可以直到这个边不是桥，则两个连通块之间必定有两外一条边，，基本思路为如此，具体证明y也不太清楚hh。

结论2：

如果度数为 1 的点的个数为 cnt 个，则需要新加 (cnt + 1) / 2 条边，可以使得此图变为边的双连通分量。

证明2：

  • 证明 ans >= (cnt + 1) / 2 : 若此图边为边的双连通分量，等价于所有点的度数 >= 2 , 即、所有度数为 1 的点都至少需要加一条边，最优先的连边策略为两个度数为 1 的点连一条边，消除两个度数为 1 的点，如果剩余一个点，此点随便连一个点即可，如此新加的边的个数的最优策略为 cnt / 2上取整，等价于 (cnt + 1) / 2 下取整，即所求新加的边 ans >= (cnt + 1) / 2 (最优解)。
  • 证明 ans == (cnt + 1) / 2 : 可知如果可以取到 (cnt + 1) / 2，则 我们所求的 ans == (cnt + 1) / 2;
    • 边界：当 只有两个点时，加一条边即可，(2 + 1) / 2 == 1 成立
    • 至少有三个点：以一个度数至少为 2 的点为根节点，则所有度数为 1 的点都为叶子节点，两个叶子节点相连，剩余一个随便连，则新加的边的数量为 (cnt + 1) / 2，也成立。
  • 大致证明为以上的叙述，，具体证明太麻烦，就此告一段落，记住结论即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_id[N], dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// from 为u是从哪条边来的
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])
        {
            tarjan(j, i); // i 为边的编号
            // 关于此处为什么判断边?
            // 首先不可武断的判断是否为父节点父节点，我们要找的是边的双连通分量，两点之间可以有多条
            // 边，可能从 x - y 之间有 a, b 两条边，从 a 边下来，又从 b 边上去，这是可行的，若直接
            // 判断点，则 b 边是不可走，错误。

            low[u] = min(low[u], low[j]);
            if(dfn[u] < low[j])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if(i != (from ^ 1)) // 边成对出现
            low[u] = min(low[u], dfn[j]);
    }
    
    if(dfn[u] == low[u])
    {
        ++ dcc_cnt;
        int y;
        do {
            y = stk[top -- ];
            dcc_id[y] = dcc_cnt;
        } while(y != u);
    }
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    tarjan(1, -1);
    
    // 直接判断所有边是不是桥，若是，则相邻的两条边的 e[i] 所在的 dcc_id都会加上 1
    for (int i = 0; i < idx; i ++ )
        if(is_bridge[i])
            d[dcc_id[e[i]]] ++;
    
    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i ++ )
        if(d[i] == 1) 
            cnt ++;
    
    printf("%d\n", (cnt + 1) / 2);
    
    return 0;
}

点双连通分量(v-DCC)

介绍

  • 割点：一个点，若删除此点，整个图变得不连通，则称这个点为“割点”
  • 点双连通分量：极大的不包含“割点”的连通块，则称为“点的双连通分量”。
  • 性质：
    1. 每一个割点都会至少属于两个点双连通分量。

Tarjan算法求点的双连通分量

  • 时间戳(timestamp)，dfn[N], low[N], 和有向图的强连通分量作用相同
  • 如何找到割点？若，对于 x - y，在 low[y] >= dfn[x] (最多只能走到父节点) 的情况下：
    • 如果 x 不是根节点，那么 x 必定是一个割点
    • 如果 x 是根节点，至少有两个子节点，那么 x 必定是一个割点
  • 如何求点的双连通分量？
    • stack实现
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      // 特判孤立点
      if (u == 孤立点)
      {
        cnt ++ ;
        此点单独为一个点的双连通分量；
      }

      if (dfn[x] <= low[y])
      {
        cnt ++ ;
        if (x != 根节点 || cnt > 1) x 是割点；
        将栈中元素弹出，直至弹出 y 为止。
        且 x 也属于此点的双连通分量。
      }
    • 证明为什么将 x 加入 y 的双连通分量中：
      • 若 dfn[x] <= low[y] 可以取到 = ，则 x 在此双连通分量是无可厚非的(必然的，正确的)
      • 若 dfn[x] < low[y] ，则 缩点后 x - y 只有一条边相连，两点一边本身就是一个点双连通分量，所以将 x 加入此双连通分量也是正确的。

例题：1183. 电力

题意：删除一个点，可以形成的最多的连通块的个数为多少？

思路：求割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int root, ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

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[u] >= dfn[u]) cnt ++; // 无法上去, 删去则多一个连通块
        }
        else low[u] = min(low[u], dfn[j]);
    }
    
    if(u != root) cnt ++; // 不是根节点，加上u的父节点的连通块( + 1 )
    
    ans = max(ans, cnt);
}

int main()
{
    while(scanf("%d%d", &n, &m), n || m)
    {
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        idx = timestamp = 0;
        
        while(m -- )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }
        
        ans = 0;
        int cnt = 0;
        for (root = 0; root < n; root ++ )
            if(!dfn[root])
            {
                cnt ++;
                tarjan(root);
            }
        
        printf("%d\n", ans + cnt - 1);
    }
    
    return 0;
}

例题：396. 矿场搭建

题意；给定一个无向图，问最少在几个点上设置出口，可以使得不管其他哪个点坍塌，其余所有点都可以与某个出口相连；

结论1：：

  • 出口数量 >= 2
  • 分别看每个连通块：
    • (v-DCC 度数为0) 若 图中无割点(无论删除哪个点，剩余部分一定为连通的)：若 cnt 为图中点的个数， ans == C(2, cnt) == cnt * (cnt - 1) / 2
    • 若 图中有割点：则需要缩点！
      • 每个割点单独作为一个点
      • 从每个 v-DCC 向其所包含的每个割点连一条边
    • v-DCC 度数为 1 ：需要在该分量内部(非割点)放一个出口
    • v-DCC 度数 > 1 ：无需设置出口

证明1：

  • 缩点过，如果割点 坍塌，已知度数为 1 的点是叶子节点，则每一颗子树至少能被自己的叶子节点所救
  • 如果度数为 1 的 v-DCC 中的某个点坍塌，可以通过割点走向另一个子树的叶子节点，从而逃脱
  • 如果度数为 2 的 v-DCC 中的某个点坍塌，可以通过走到任意的一个割点从而走到子树的叶子节点，从而逃脱

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef unsigned long long ULL;

const int N = 1010, M = 1010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

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); // 加到 j 即可，不可加到 u ，可能有其他子树
                dcc[dcc_cnt].push_back(u); // 最后补加一个割点
            }
        }
        else low[u] = min(low[u], dfn[j]);
    }
}

int main()
{
    int T = 0;
    while(cin >> m, m)
    {
        for (int i = 1; i <= dcc_cnt; i ++ ) dcc[i].clear();
        idx = n = timestamp = top = dcc_cnt = 0;
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(cut, 0, sizeof cut);
        
        while(m -- )
        {
            int a, b;
            cin >> a >> b;
            n = max(n, a), n = max(n, b);
            add(a, b), add(b, a);
        }
        
        for (root = 1; root <= n; root ++ )
            if(!dfn[root])
                tarjan(root);
        
        int res = 0;
        ULL num = 1;
        for (int i = 1; i <= dcc_cnt; i ++ )
        {
            int cnt = 0;
            for (int j = 0; j < dcc[i].size(); j ++ )
                if(cut[dcc[i][j]])
                    cnt ++;
            
            if(cnt == 0)
            {
                if(dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                else res ++;
            }
            else if(cnt == 1) res ++, num *= dcc[i].size() - 1;
        }
        
        printf("Case %d: %d %llu\n", ++ T, res, num);
    }
    
    return 0;
}