Bỏ qua

Thành phần song liên thông (BCC)

Giới thiệu

Trước khi đọc nội dung dưới đây, bạn cần nắm vững phần Các khái niệm liên quan đến lý thuyết đồ thị.

Đọc thêm: Điểm cắt và cầu

Định nghĩa

Định nghĩa chính xác về điểm cắt và cầu xem tại Các khái niệm liên quan đến lý thuyết đồ thị.

Trên một đồ thị vô hướng liên thông, với hai đỉnh \(u\) và \(v\), nếu bất kể xóa cạnh nào (chỉ được xóa một cạnh) cũng không thể làm chúng bị ngắt kết nối, ta nói \(u\) và \(v\) cạnh hai phía liên thông (edge-biconnected).

Trên một đồ thị vô hướng liên thông, với hai đỉnh \(u\) và \(v\), nếu bất kể xóa đỉnh nào (chỉ được xóa một đỉnh, không xóa chính \(u\) hoặc \(v\)) cũng không thể làm chúng bị ngắt kết nối, ta nói \(u\) và \(v\) đỉnh hai phía liên thông (vertex-biconnected).

Tính chất truyền: cạnh hai phía liên thông có tính chất truyền, tức là nếu \(x,y\) cạnh hai phía liên thông, \(y,z\) cạnh hai phía liên thông thì \(x,z\) cũng cạnh hai phía liên thông.

Đỉnh hai phía liên thông không có tính chất truyền. Ví dụ dưới đây: \(A,B\) đỉnh hai phía liên thông, \(B,C\) đỉnh hai phía liên thông, nhưng \(A,C\) không đỉnh hai phía liên thông.

bcc-counterexample.png

Một tiểu đồ thị cạnh hai phía liên thông cực đại gọi là thành phần cạnh hai phía liên thông.

Một tiểu đồ thị đỉnh hai phía liên thông cực đại gọi là thành phần đỉnh hai phía liên thông.

Cây DFS

Với một đồ thị vô hướng liên thông, ta có thể bắt đầu DFS từ bất kỳ đỉnh nào để thu được một cây DFS (gốc là đỉnh bắt đầu), các cạnh thuộc cây này gọi là cạnh cây, các cạnh không thuộc cây gọi là cạnh ngoài cây.

Do tính chất của DFS, mọi cạnh ngoài cây đều nối hai đỉnh mà một đỉnh là tổ tiên của đỉnh còn lại trên cây.

Mã nguồn DFS như sau:

Cài đặt 
1
2
3
4
5
void DFS(int p) {
  visited[p] = true;
  for (int to : edge[p])
    if (!visited[to]) DFS(to);
}

1
2
3
4
5
def DFS(p):
    visited[p] = True
    for to in edge[p]:
        if visited[to] == False:
            DFS(to)

Thành phần cạnh hai phía liên thông

Bài mẫu: LuoGu P8436【Mẫu】Thành phần cạnh hai phía liên thông

Cho một đồ thị vô hướng \(n\) đỉnh \(m\) cạnh, hãy xuất số lượng thành phần cạnh hai phía liên thông và liệt kê từng thành phần.

Thuật toán Tarjan 1

Dùng Tarjan để tìm thành phần hai phía liên thông tương tự như tìm thành phần liên thông mạnh, có thể xem trước Thành phần liên thông mạnh với thuật toán Tarjan.

Ta sẽ tìm tất cả các cầu trước, sau đó DFS để tìm thành phần cạnh hai phía liên thông.

Cách tìm cầu xem tại Điểm cắt và cầu.

Độ phức tạp \(O(n+m)\).

Mã nguồn mẫu 
 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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m, ans;
int tot = 1, hd[N];

struct edge {
  int to, nt;
} e[M << 1];

void add(int u, int v) { e[++tot].to = v, e[tot].nt = hd[u], hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

bool bz[M << 1];
int bcc_cnt, dfn[N], low[N], vis_bcc[N];
vector<vector<int>> bcc;

void tarjan(int x, int in) {
  dfn[x] = low[x] = ++bcc_cnt;
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (dfn[v] == 0) {
      tarjan(v, i);
      if (dfn[x] < low[v]) bz[i] = bz[i ^ 1] = true;
      low[x] = min(low[x], low[v]);
    } else if (i != (in ^ 1))
      low[x] = min(low[x], dfn[v]);
  }
}

void dfs(int x, int id) {
  vis_bcc[x] = id, bcc[id - 1].push_back(x);
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (vis_bcc[v] || bz[i]) continue;
    dfs(v, id);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u == v) continue;
    uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (dfn[i] == 0) tarjan(i, 0);
  for (int i = 1; i <= n; i++)
    if (vis_bcc[i] == 0) {
      bcc.push_back(vector<int>());
      dfs(i, ++ans);
    }
  cout << ans << '\n';
  for (int i = 0; i < ans; i++) {
    cout << bcc[i].size();
    for (int j = 0; j < bcc[i].size(); j++) cout << ' ' << bcc[i][j];
    cout << '\n';
  }
  return 0;
}

Thuật toán Tarjan 2

Tổng kết một tính chất quan trọng: trên đồ thị vô hướng, cạnh cây và cạnh ngoài cây là hai loại duy nhất.

Liên hệ với cách tìm thành phần liên thông mạnh: trên đồ thị vô hướng, nếu một thành phần không có cầu, thì trên cây DFS, tất cả các đỉnh thuộc cùng một thành phần liên thông mạnh.

Ngược lại, một thành phần liên thông mạnh trên cây DFS chính là một thành phần cạnh hai phía liên thông trên đồ thị gốc.

Vậy quá trình tìm thành phần cạnh hai phía liên thông thực chất là quá trình tìm thành phần liên thông mạnh.

Độ phức tạp \(O(n+m)\).

Mã nguồn mẫu 
 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
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 2];

int hd[N << 1], tot = 1;

void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

int bcc_cnt, sum;
int dfn[N], low[N];
bool vis[N];
vector<vector<int>> ans;
stack<int> st;

void tarjan(int u, int in) {
  low[u] = dfn[u] = ++bcc_cnt;
  st.push(u), vis[u] = true;
  for (int i = hd[u]; i; i = e[i].nt) {
    int v = e[i].to;
    if (i == (in ^ 1)) continue;
    if (!dfn[v])
      tarjan(v, i), low[u] = min(low[u], low[v]);
    else if (vis[v])
      low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    vector<int> t;
    t.push_back(u);
    while (st.top() != u)
      t.push_back(st.top()), vis[st.top()] = false, st.pop();
    st.pop(), ans.push_back(t);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u != v) uadd(u, v);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i, 0);
  cout << ans.size() << '\n';
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].size() << ' ';
    for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

Thuật toán hiệu ứng chênh lệch (difference)

Tương tự Tarjan 1, ta tìm tất cả các cầu trước, sau đó dùng hiệu ứng chênh lệch để tìm thành phần cạnh hai phía liên thông.

Đầu tiên, thực hiện DFS trên đồ thị gốc.

bcc-1.png

Trong hình, cạnh đen và xanh lá là cạnh cây, cạnh đỏ là cạnh ngoài cây. Mỗi cạnh ngoài cây nối hai đỉnh, tương ứng duy nhất với một đường đi đơn giản trên cây gồm các cạnh cây, ta nói cạnh ngoài cây phủ lên tất cả các cạnh cây trên đường đi đó.

Trong hình, cạnh cây xanh lá ít nhất được một cạnh ngoài cây phủ, cạnh cây đen không được bất kỳ cạnh ngoài cây nào phủ.

Rõ ràng, cạnh ngoài cây và cạnh cây xanh lá chắc chắn không phải cầu, cạnh cây đen chắc chắn là cầu.

Xét một cách vét cạn: với mỗi cạnh ngoài cây, duyệt từng cạnh cây trên đường đi và đánh dấu là xanh lá, độ phức tạp \(O(nm)\).

Dùng hiệu ứng chênh lệch để tối ưu: với mỗi cạnh ngoài cây, tại đỉnh sâu hơn trên cây DFS đánh dấu +1, tại đỉnh cạn hơn đánh dấu -1, sau đó \(O(n)\) để tính tổng hiệu ứng trong mỗi cây con.

Với một đỉnh \(u\), tổng hiệu ứng trong cây con bằng số lượng cạnh ngoài cây phủ lên cạnh cây giữa \(u\) và \(fa_u\). Nếu giá trị này bằng \(0\), cạnh cây giữa \(u\) và \(fa_u\) là cầu.

Sau đó DFS để tìm thành phần cạnh hai phía liên thông.

Độ phức tạp \(O(n+m)\).

Mã nguồn mẫu 
 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
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 1];

int hd[N], tot;

void add(int u, int v) { e[++tot] = {v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }  // 链式前向星

using ll = long long;
#define P(x, y) ((ll)min(x, y) * N + (ll)max(x, y))
constexpr int hmod = 1e5 + 7;

struct hash {
  vector<ll> v1[hmod];
  vector<short> v2[hmod];

  short &operator[](ll x) {
    int y = x % hmod;
    for (int i = 0; i < v1[y].size(); i++)
      if (v1[y][i] == x) return v2[y][i];
    v1[y].push_back(x), v2[y].push_back(0);
    return v2[y].back();
  }
} re, be;  // 用 vector 实现 hash 表，因为本题时空限制均比较紧

// re 判断是否有重边，be 记录边是不是桥

// #define P(x, y) {min(x, y), max(x, y)}
// using pii = pair<int, int>;
// map<pii, int> re, be; // 不紧时可以用 map 实现 hash 表

int dep[N], bz[N], sum[N];  // 记录深度、差分值、子树查分和
int vis[N], fa[N];          // 记录是否访问过，分组编号

void dfs(int x, int pre) {  // 计算每个点的深度和单点查分
  if (dep[x] < dep[pre]) bz[x]++, bz[pre]--;  // 回到祖先，更改差分值
  if (dep[x]) return;
  dep[x] = dep[pre] + 1;
  for (int i = hd[x]; i; i = e[i].nt) dfs(e[i].to, x);
}

int dfs2(int x, int pre) {  // 处理子树查分
  if (vis[x] == 1) return sum[x];
  vis[x] = 1, sum[x] = bz[x];
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (dep[v] > dep[x] && !vis[v]) sum[x] += dfs2(v, x);
  }
  if (sum[x] == 0 && re[P(x, pre)] == 1) be[P(x, pre)] = 1;  // 记录桥
  return sum[x];
}

int cnt;
vector<int> ans[N];

void dfs3(int x) {  // 计算双连通分量
  if (fa[x]) return;
  ans[cnt].push_back(x), fa[x] = cnt;
  for (int i = hd[x]; i; i = e[i].nt) {
    int v = e[i].to;
    if (be[P(x, v)] != 1) dfs3(v);  // 不是桥，递归处理子树
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) cin >> u >> v, uadd(u, v), re[P(u, v)]++;
  for (int i = 1; i <= n; i++)
    if (!dep[i]) dfs(i, 0);
  for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs2(i, 0);
  for (int i = 1; i <= n; i++)
    if (!fa[i]) cnt++, dfs3(i);
  cout << cnt << '\n';
  for (int i = 1; i <= cnt; i++) {
    cout << ans[i].size() << ' ';
    for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}
#2788.「CEOI2015 Day1」Ống dẫn

Cho một đồ thị vô hướng \(N\) đỉnh \(M\) cạnh, không đảm bảo liên thông. Xem mỗi thành phần liên thông là một đồ thị con, hãy tìm các cầu trong từng đồ thị con. Chỉ có 16 MB bộ nhớ.

Phân tích

Đặc điểm lớn nhất của bài này là không đủ bộ nhớ để lưu tất cả các cạnh.

Xét tối ưu lưu cạnh: nếu một cạnh ngoài cây bị một cạnh ngoài cây khác phủ hoàn toàn, thì cạnh đó không cần thiết.

Dùng cấu trúc hợp nhất (union-find) để quản lý.

Thành phần đỉnh hai phía liên thông

Bài mẫu: LuoGu P8435【Mẫu】Thành phần đỉnh hai phía liên thông

Cho một đồ thị vô hướng \(n\) đỉnh \(m\) cạnh, hãy xuất số lượng thành phần đỉnh hai phía liên thông và liệt kê từng thành phần.

Thuật toán Tarjan

Cần học về điểm cắt trước, xem tại Điểm cắt và cầu phần điểm cắt.

Hai tính chất:

  1. Hai thành phần đỉnh hai phía liên thông tối đa chỉ có một đỉnh chung, và đó chắc chắn là điểm cắt.
  2. Với một thành phần đỉnh hai phía liên thông, trên cây DFS, đỉnh có dfn nhỏ nhất chắc chắn là điểm cắt hoặc là gốc cây.

Theo tính chất thứ hai, phân thành các trường hợp:

  1. Nếu đỉnh đó là điểm cắt, nó chắc chắn là gốc của thành phần đỉnh hai phía liên thông, vì nếu chứa cha của nó thì nó vẫn là điểm cắt.
  2. Nếu đỉnh đó là gốc cây:
    1. Có từ hai cây con trở lên, nó là điểm cắt.
    2. Chỉ có một cây con, nó là gốc của thành phần đỉnh hai phía liên thông.
    3. Không có cây con, coi như một thành phần đỉnh hai phía liên thông.
Mã nguồn mẫu 
 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
#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge {
  int to, nt;
} e[M << 1];

int hd[N], tot = 1;

void add(int u, int v) { e[++tot] = edge{v, hd[u]}, hd[u] = tot; }

void uadd(int u, int v) { add(u, v), add(v, u); }

int ans;
int dfn[N], low[N], bcc_cnt;
int sta[N], top, cnt;
bool cut[N];
vector<int> dcc[N];
int root;

void tarjan(int u) {
  dfn[u] = low[u] = ++bcc_cnt, sta[++top] = u;
  if (u == root && hd[u] == 0) {
    dcc[++cnt].push_back(u);
    return;
  }
  int f = 0;
  for (int i = hd[u]; i; i = e[i].nt) {
    int v = e[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        if (++f > 1 || u != root) cut[u] = true;
        cnt++;
        do dcc[cnt].push_back(sta[top--]);
        while (sta[top + 1] != v);
        dcc[cnt].push_back(u);
      }
    } else
      low[u] = min(low[u], dfn[v]);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    if (u != v) uadd(u, v);
  }
  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 (int j = 0; j < dcc[i].size(); j++) cout << dcc[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

Thuật toán hiệu ứng chênh lệch

bcc-2.png

Trong hình, cạnh đen là cạnh cây, cạnh đỏ là cạnh ngoài cây, mỗi cạnh ngoài cây nối hai đỉnh, tương ứng duy nhất với một đường đi đơn giản trên cây gồm các cạnh cây.

Xét một đồ thị mới, mỗi đỉnh trong đồ thị mới tương ứng với một cạnh cây trong đồ thị gốc (biểu diễn bằng các điểm xanh dương trong hình). Với mỗi cạnh ngoài cây, nối các điểm xanh dương tương ứng với các cạnh cây trên đường đi thành một thành phần liên thông (biểu diễn bằng các cạnh xanh dương).

Như vậy, một đỉnh không phải là điểm cắt khi và chỉ khi các cạnh cây nối với nó trong đồ thị mới đều thuộc cùng một thành phần liên thông.

Hai đỉnh là đỉnh hai phía liên thông khi và chỉ khi các cạnh cây trên đường đi giữa chúng trong đồ thị mới đều thuộc cùng một thành phần liên thông, tức là mỗi thành phần liên thông của các điểm xanh dương là một thành phần đỉnh hai phía liên thông.

Quan hệ liên thông giữa các điểm xanh dương có thể quản lý bằng hiệu ứng chênh lệch như khi tìm thành phần cạnh hai phía liên thông, độ phức tạp \(O(n+m)\)

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply