连通性问题

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 10 分钟

连通性问题

tarjan：连通性问题永远的神。

双连通与割点、割边

  • 点双连通：在无向图中，删除一个点（不是 xx 或者 yy）后，点 xx 和点 yy 仍然能够彼此到达，那么称 xx 和 yy 是点双连通的；

  • 边双连通：在无向图中，删除一条边后，点 xx 和点 yy 仍然能够彼此到达，那么称 xx 和 yy 是边双连通的；

  • 性质 11： 点双连通不具有传递性，但边双连通具有传递性；

  • 割点

    • 在无向图 GG 中，若删除 xx 后，连通块的数量增加，则 xx 称为无向图 GG 的一个割点（割顶）。

    • 结论：至少有 33 个点的无向图，才可能存在割点；

    • 割点的判定

      • 若搜索树中，有从 xx 到 yy 的连边，当 lowy≥dfnxlow_y \ge dfn_x 时，说明 yy 能到达的最小时间戳在 xx 的时间戳之上，yy 被 xx 与 xx 之前的结点“隔开”，xx 可能是割点。只要 xx 不是搜索树的根结点，或者 xx 是根结点，但是 xx 的子结点大于 11 个，那么 xx 就是割点。
      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        void tarjan(int x)
        {
            dfn[x] = low[x] = ++num; //打时间戳
            int cnt = 0; //统计子 结点个数
            for (auto& [nxt, w] : nbr[x])
                if (!dfn[nxt]) //没去过 $nxt$
                {
                    tarjan(nxt); //递归查找
                    low[x] = min(low[x], low[nxt]); //维护 $x$ 能达到的最小时间戳 $low_X$
                    cnt++;
                    if (low[nxt] >= dfn[x]) //$x$ 可能是割点
                        if (x != root || cnt >= 2) //排除根 结点只有 $1$个子 结点
                            cut[x] = true;
                }
                else //$nxt$ 去过，所以 $nxt$ 还没有回溯，不能用 $low_nxt$
                    low[x] = min(low[x], dfn[nxt]);
            return;
        }

  • 割边

    • 在无向图中，若删除 11 条边 ee 后，连通块的数量增加，那么称 ee 为一条割边。

    • 性质：割边一定不在环上，在环上的边一定不是割边。

    • 割边涉及的通常是“必经边”的问题。

    • 不用证明：割边删除后，恰好增加 11 个连通块。

    • 割边的判定

      • 维护 dfnxdfn_x 和 lowxlow_x 之后，对于 xx 到 yy 的连边，若 lowy>dfnxlow_y > dfn_x，则 bridge[i] = bridge[i^1] = true（对于链式前向星的方法）。

      • 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
        #include<bits/stdc++.h>
        typedef int int32;
        #define int long long
        using namespace std;
        const int N = 1e6 + 5;
        int n, m, dfn[N], low[N], num, ans;
        bool cut[N];
        vector<pair<int, int>>nbr[N];
        void tarjan(int x, int edge)
        {
        	dfn[x] = low[x] = ++num;
        	for (auto& [nxt, w] : nbr[x])//这里的 $w$ 不是权值，是边的编号
        		if (!dfn[nxt])
        		{
        			tarjan(nxt, w);
        			low[x] = min(low[x], low[nxt]);
        			if (low[nxt] > dfn[x])
        				cut[w] = true;
        		}
        		else if (w != edge)
        			low[x] = min(low[x], dfn[nxt]);
        	return;
        }
        signed main()
        {
        	ios::sync_with_stdio(0);
        	cin.tie(0), cout.tie(0);
        	cin >> n >> m;
        	for (int i = 1; i <= m; i++)
        	{
        		int x, y, z = i;
        		cin >> x >> y;
        		nbr[x].push_back({ y,z });
        		nbr[y].push_back({ x,z });
        	}
        	for (int i = 1; i <= n; i++)
        		if (!dfn[i])
        			tarjan(i, 0);
        	for (int i = 1; i <= m; i++)
        		ans += cut[i];
        	cout << ans;
        	return 0;
        }

例题

洛谷P3388

P3388 【模板】割点（割顶）

题意：给出一个 nn 个点，mm 条边的无向图，求图的割点。

CF22C

题意：构造 nn 个点 mm 条边的无向连通图，且无重边，点 vv 必须是割点。需特判无解。

  1. 有解时，mm 一定有上界和下界，下届为 m≥n−1m \ge n-1；
  2. vv 已经连接了 n−1n-1 个点，不能有重边，因此 vv 不能再连边，视为 vv 不存在；
  3. 为了保证容纳的边尽可能多，要尽量连完全图，且不能破坏 vv 的割点特征；
  4. 留 11 个单点只跟 vv 保持连边，剩下的 n−2n-2 个点构造完全图即可；
  5. 上界 m≤n−1+(n−2)×(n−3)/2m \le n-1+ (n-2)\times(n-3)/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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, v;
#define print(x, y) cout << x << ' ' << y << '\n'
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> v;
	if (m < n - 1 || m > n - 1 + (n - 2) * (n - 3) / 2)
		cout << -1;
	else
	{
		m -= n - 1;
		if (v == 1)
		{
			print(1, 2);
			print(1, 3);
			for (int i = 3; i < n; i++)
				print(i, i + 1);
			for (int i = 3; i <= n; i++)
				for (int j = i + 2; j <= n; j++)
					if (m--)
						print(i, j);
					else
						goto end;//不建议使用 `goto`，我是为了方便。
			for (int i = 4; i <= n; i++)
				if (m--)
					print(i, 1);
				else
					goto end;
		}
		else
		{
			for (int i = 2; i < n; i++)
				print(i, i + 1);
			print(1, v);
			for (int i = 2; i <= n; i++)
				for (int j = i + 2; j <= n; j++)
					if (m--)
						print(i, j);
					else
						goto end;
		}
	end:;
	}
	return 0;
}

洛谷P3469

P3469 BLO-Blockade

题意：对于每个结点 ii 求出，把与结点 ii 关联的所有边去掉以后（不去掉结点 ii 本身），无向图有多少个有序点 (x,y)(x,y)，满足 xx 和 yy 不连通。

  • 一个点 xx，如果是不是割点，那么贡献一定是 (n−2)÷2(n-2) \div 2；否则贡献是 (n−1)+(z+1)(n−z−1)+∑y=Aiy(n−y)(n-1)+(z+1)(n-z-1)+\sum_{y = A_i}{y(n-y)}。其中 AiA_i 为 结点 ii 满足：ii 是 xx 的子 结点，ii 之前没有访问过且 lowi≥dfnxlow_i \ge dfn_x；zz 为 ∑ai\sum a_i。
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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, dfn[N], low[N], num, root, ans[N], sum[N];
bool cut[N];
vector<pair<int, int>>nbr[N];
void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
	sum[x] = 1;
	int cnt = 0, tot = 0;
	for (auto& [nxt, w] : nbr[x])
		if (!dfn[nxt])
		{
			tarjan(nxt);
			sum[x] += sum[nxt];
			low[x] = min(low[x], low[nxt]);
			cnt++;
			if (low[nxt] >= dfn[x])
			{
				ans[x] += sum[nxt] * (n - sum[nxt]);
				tot += sum[nxt];
				if (x != root || cnt >= 2)
					cut[x] = true;
			}
		}
		else
			low[x] = min(low[x], dfn[nxt]);
	if (!cut[x])
		ans[x] = 2 * (n - 1);
	else
		ans[x] += (n - tot - 1) * (tot + 1) + (n - 1);
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z = 1;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			root = i, tarjan(i);
	for (int i = 1; i <= n; i++)
		cout << ans[i] << '\n';
	return 0;
}

洛谷P1656

P1656 炸铁路

题意：求割边，模板题。

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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, dfn[N], low[N], num, ans, cnt;
bool cut[N];
vector<pair<int, int>>nbr[N];
pair<int, int>a[N], b[N];
void tarjan(int x, int edge)
{
	dfn[x] = low[x] = ++num;
	for (auto& [nxt, w] : nbr[x])
		if (!dfn[nxt])
		{
			tarjan(nxt, w);
			low[x] = min(low[x], low[nxt]);
			if (low[nxt] > dfn[x])
				cut[w] = true;
		}
		else if (w != edge)
			low[x] = min(low[x], dfn[nxt]);
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z = i;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
		a[i] = { min(x,y),max(x,y) };
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i, 0);
	for (int i = 1; i <= m; i++)
		if (cut[i])
			b[++cnt] = a[i];
	sort(b + 1, b + 1 + cnt);
	for (int i = 1; i <= cnt; i++)
		cout << b[i].first << ' ' << b[i].second << '\n';
	return 0;
}

洛谷P7687

P1656

  1. 初始时，所有点都能访问 A 和 B 类服务；
  2. 如果一条边，非割边，意味着在环上，删除后不改变连通性，不可能是关键边；
  3. 关键边应该是割边的一个子集；
  4. 对于 xx 到 yy 的连边，两侧不能出现没有 A 或者没有 B 类服务的点；
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
#include<bits/stdc++.h>
typedef int int32;
//#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, m, dfn[N], low[N], num, ans, a[N], b[N], k, l;
bool cut[N], vis[N];
vector<pair<int, int>>nbr[N];
pair<int, int>c[N];
void tarjan(int x, int edge)
{
	dfn[x] = low[x] = ++num;
	for (auto& [nxt, w] : nbr[x])
		if (!dfn[nxt])
		{
			tarjan(nxt, w);
			a[x] += a[nxt];
			b[x] += b[nxt];
			low[x] = min(low[x], low[nxt]);
			if (low[nxt] > dfn[x])
			{
				cut[w] = true;
				if (max(a[nxt], k - a[nxt]) == k || max(b[nxt], l - b[nxt]) == l)
					vis[w] = true;
			}
		}
		else if (w != edge)
			low[x] = min(low[x], dfn[nxt]);
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k >> l;
	for (int i = 1; i <= k; i++)
	{
		int x;
		cin >> x;
		a[x] = 1;
	}
	for (int i = 1; i <= l; i++)
	{
		int x;
		cin >> x;
		b[x] = 1;
	}
	for (int i = 1; i <= m; i++)
	{
		int x, y, z = i;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
		c[i] = { x,y };
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i, 0);
	for (int i = 1; i <= m; i++)
		ans += vis[i];
	cout << ans << '\n';
	for (int i = 1; i <= m; i++)
		if (vis[i])
			cout << c[i].first << ' ' << c[i].second << '\n';
	return 0;
}

边双连通分量

  • 边双连通：若无向图中点 xx 和 yy 在删除任意连边后，仍然连通，称 xx 和 yy 是边双连通的；
  • 边双连通分量：若无向图 GG 中，存在一个极大子图 G′G'，G′G' 中没有割边，那么 G′G' 是 GG 的一个边双连通分量记为 E-DCC；

例题

洛谷T103489

T103489 【模板】边双连通分量

题意：给定一个 nn 个点 mm 条边的无向图，求边双连通分量（e-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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, m, dfn[N], low[N], num, ans, cnt, dcc[N], id;
bool cut[N];
vector<pair<int, int>>nbr[N];
pair<int, int>a[N];
void tarjan(int x, int edge)
{
	dfn[x] = low[x] = ++num;
	for (auto& [nxt, w] : nbr[x])
		if (!dfn[nxt])
		{
			tarjan(nxt, w);
			low[x] = min(low[x], low[nxt]);
			if (low[nxt] > dfn[x])
				cut[w] = true;
		}
		else if (w != edge)
			low[x] = min(low[x], dfn[nxt]);
	return;
}
void dfs(int x)
{
	dcc[x] = id;
	for (auto& [nxt, w] : nbr[x])
		if (!dcc[nxt] && !cut[w])
			dfs(nxt);
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z = i;
		cin >> x >> y;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
		a[i] = { min(x,y),max(x,y) };
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i, 0);
	for (int i = 1; i <= n; i++)
		if (!dcc[i])
			id++, dfs(i);
	cout << id;
	return 0;
}

CF51F

  1. 图可能不连通，视为多个毛毛虫的拼接，每两个操作 11 次；
  2. 对于一张连通图， 缩边双连通分量变为一棵树；
  3. 对于一棵树，操作叶子结点不会比操作叶子的父结点更优，所以叶子结点保留；
  4. 保留的主链越长越好，取树的直径最优，设长度为 lenlen，且子结点为 cntcnt 个，n−len−cnt+2n-len-cnt+2；
  5. 设一个边双的结点数为 sizesize，一个边双需要操作 size−1size-1 次；

点双连通分量

  • 点双连通：无向图中，若点 xx 和 yy，在删除任一点 zz（z≠x,z≠yz\not=x, z\not=y）后，xx 和 yy 仍然连通，那么称点 xx 和 yy 是点双连通的。

  • 点双连通分量：无向图 GG 中，若存在极大子图 G′G'，G′G' 中没有割点，那么 G′G' 称之为 GG 的一个点双连通分量，记为 V-DCC。

推论：

  • 边双连通分量由割边连接，所以一个点只能在 11 个 E-DCC 里；

  • 点双连通分量由割点链接，而 11 个点可以链接多条边，因此 11 个点可以在多个 V-DCC 里；

  • 若 11 个点在超过 11 个 V-DCC 中，则该点一定是割点；

  • 当研究一个 V-DCC 时，其内部没有“割点”，当研究整个图时，多个 V-DCC 的交点就是割点；

  • 一条边只能在一个 V-DCC 中。

例题

洛谷P8435

P8435 【模板】点双连通分量

题意：对于一个 nn 个节点 mm 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 2e6 + 5;
int n, m, dfn[N], low[N], num, root, cnt;
bool cut[N];
vector<pair<int, int>>nbr[N];
vector<int>dcc[N];
stack<int>q;
void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
	q.push(x);
	if (x == root && !nbr[x].size())//x是单点
	{
		dcc[++cnt].push_back(x);
		return;
	}
	int tot = 0;
	for (auto& [nxt, w] : nbr[x])
		if (!dfn[nxt])
		{
			tarjan(nxt);
			low[x] = min(low[x], low[nxt]);
			if (low[nxt] >= dfn[x])
			{
				tot++;
				if (x != root || tot >= 2)
					cut[x] = true;
				int tmp = 0;
				cnt++;
				while (!q.empty() && tmp != nxt)
				{
					tmp = q.top();
					q.pop();
					dcc[cnt].push_back(tmp);
				}
				dcc[cnt].push_back(x);
			}
		}
		else
			low[x] = min(low[x], dfn[nxt]);
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z = 1;
		cin >> x >> y;
		if (x == y)
			continue;
		nbr[x].push_back({ y,z });
		nbr[y].push_back({ x,z });
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			root = i, tarjan(i);
	cout << cnt << '\n';
	for (int i = 1; i <= cnt; i++)
	{
		cout << dcc[i].size() << ' ';
		for (auto& x : dcc[i])
			cout << x << ' ';
		cout << '\n';
	}
	return 0;
}