Bỏ qua

Khớp & Cầu

Đọc thêm: Thành phần hai phía liên thông

Đị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ị.

Điểm cắt

Trên một đồ thị vô hướng, nếu khi xóa một đỉnh mà số lượng thành phần liên thông cực đại của đồ thị tăng lên, thì đỉnh đó gọi là điểm cắt (hay còn gọi là điểm khớp).

Quy trình

Nếu thử xóa từng đỉnh rồi kiểm tra liên thông, độ phức tạp sẽ rất cao. Vì vậy, ta dùng một thuật toán phổ biến: Tarjan.

Trước hết, xét một đồ thị:

Dễ thấy điểm cắt là đỉnh 2, và đồ thị này chỉ có một điểm cắt.

Đánh số thứ tự truy cập (DFS order) cho các đỉnh:

Thông tin này lưu trong mảng dfn.

Cần thêm mảng low, dùng để lưu thời điểm truy cập nhỏ nhất mà đỉnh đó có thể đến được mà không qua cha.

Ví dụ: low[2] = 1, low[5] và low[6] = 3.

Khi DFS, điều kiện để một đỉnh \(u\) là điểm cắt: tồn tại ít nhất một đỉnh con \(v\) của \(u\) sao cho \(low_v \geq dfn_u\), tức là không thể quay lại tổ tiên, khi đó \(u\) là điểm cắt.

Trường hợp đặc biệt với đỉnh gốc: nếu không phải điểm cắt thì mọi đường đi đều có thể đến mọi đỉnh, tức là trong cây DFS chỉ có một con. Nếu có từ hai con trở lên thì chắc chắn là điểm cắt (ví dụ, nếu bắt đầu DFS từ 2, cây sẽ có hai con: 3 hoặc 4 và 5 hoặc 6). Nếu chỉ có một con thì xóa đi không ảnh hưởng gì. Ví dụ dưới đây tạo thành một chu trình.

Khi duyệt con của 1, giả sử DFS đến 2 trước, đánh dấu đã truy cập, rồi đệ quy xuống 4, 4 lại đến 3, khi quay lại sẽ thấy 3 đã truy cập, nên không phải điểm cắt.

Cập nhật mảng low theo giả mã sau:

\[ \begin{array}{ll} 1 & \textbf{if } v \text{ là con của } u \\ 2 & \qquad \text{low}_u = \min(\text{low}_u, \text{low}_v) \\ 3 & \textbf{else} \\ 4 & \qquad \text{low}_u = \min(\text{low}_u, \text{dfn}_v) \\ \end{array} \]

Bài mẫu

Luogu P3388【Mẫu】Điểm cắt (điểm khớp)

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
/*
洛谷 P3388 【模板】割点（割顶）
*/
#include <iostream>
#include <vector>
using namespace std;
int n, m;  // n：点数 m：边数
int dfn[100001], low[100001], idx, res;
// dfn：记录每个点的时间戳
// low：能不经过父亲到达最小的编号，idx：时间戳，res：答案数量
bool vis[100001], flag[100001];  // flag: 答案 vis：标记是否重复
vector<int> edge[100001];        // 存图用的

void Tarjan(int u, int fa) {  // u 当前点的编号，fa 自己爸爸的编号
  vis[u] = true;              // 标记
  low[u] = dfn[u] = ++idx;    // 打上时间戳
  int child = 0;              // 每一个点儿子数量
  for (const auto &v : edge[u]) {  // 访问这个点的所有邻居 （C++11）
    if (!vis[v]) {
      child++;                       // 多了一个儿子
      Tarjan(v, u);                  // 继续
      low[u] = min(low[u], low[v]);  // 更新能到的最小节点编号
      if (fa != u && low[v] >= dfn[u] && !flag[u]) {  // 主要代码
        // 如果不是自己，且不通过父亲返回的最小点符合割点的要求，并且没有被标记过
        // 要求即为：删了父亲连不上去了，即为最多连到父亲
        flag[u] = true;
        res++;  // 记录答案
      }
    } else if (v != fa) {
      // 如果这个点不是自己的父亲，更新能到的最小节点编号
      low[u] = min(low[u], dfn[v]);
    }
  }
  // 主要代码，自己的话需要 2 个儿子才可以
  if (fa == u && child >= 2 && !flag[u]) {
    flag[u] = true;
    res++;  // 记录答案
  }
}

int main() {
  cin >> n >> m;                  // 读入数据
  for (int i = 1; i <= m; i++) {  // 注意点是从 1 开始的
    int x, y;
    cin >> x >> y;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }  // 使用 vector 存图
  for (int i = 1; i <= n; i++)  // 因为 Tarjan 图不一定连通
    if (!vis[i]) {
      idx = 0;       // 时间戳初始为 0
      Tarjan(i, i);  // 从第 i 个点开始，父亲为自己
    }
  cout << res << endl;
  for (int i = 1; i <= n; i++)
    if (flag[i]) cout << i << " ";  // 输出结果
  return 0;
}

Cầu (trường hợp không có cạnh lặp)

Tương tự điểm cắt, cầu còn gọi là cạnh cắt.

Trên một đồ thị vô hướng, nếu khi xóa một cạnh mà số lượng thành phần liên thông tăng lên, thì cạnh đó gọi là cầu (cạnh cắt). Chính xác: với đồ thị liên thông \(G=\{V,E\}\), \(e\) là một cạnh (\(e \in E\)), nếu \(G-e\) không liên thông thì \(e\) là cầu của \(G\).

Ví dụ:

Ví dụ cầu

Các cạnh đỏ là cầu.

Quy trình

Tương tự điểm cắt, chỉ cần thay điều kiện: \(low_v > dfn_u\), không cần xét trường hợp gốc.

Cầu không liên quan đến gốc, khi tìm điểm cắt thì \(v\) không thể quay lại tổ tiên (kể cả cha), nên \(u\) là điểm cắt. Nếu \(low_v = dfn_u\) thì vẫn có thể quay lại cha. Nếu \(v\) không thể quay lại tổ tiên và không có đường nào về cha, thì cạnh \(u-v\) là cầu.

Cài đặt

Đoạn mã dưới đây tìm cầu trên đồ thị vô hướng không có cạnh lặp, khi isbridge[x] đúng thì cạnh (father[x],x) là cầ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
int low[MAXN], dfn[MAXN], idx;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  bool flag = false;
  father[u] = fa;
  low[u] = dfn[u] = ++idx;
  for (const auto &v : G[u]) {
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else {
      if (v != fa || flag)
        low[u] = min(low[u], dfn[v]);
      else
        flag = true;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
low = [0] * MAXN
dfn = [0] * MAXN
idx = 0
isbridge = [False] * MAXN
G = [[0 for i in range(MAXN)] for j in range(MAXN)]
cnt_bridge = 0
father = [0] * MAXN


def tarjan(u, fa):
    father[u] = fa
    idx = idx + 1
    low[u] = dfn[u] = idx
    for i in range(0, len(G[u])):
        v = G[u][i]
        if dfn[v] == False:
            tarjan(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > dfn[u]:
                isbridge[v] = True
                cnt_bridge = cnt_bridge + 1
        elif v != fa:
            low[u] = min(low[u], dfn[v])

Cầu (trường hợp có cạnh lặp)

Cách trên không áp dụng cho đồ thị có cạnh lặp.

Vì giữa hai đỉnh có thể có nhiều cạnh, khi đó không cạnh nào là cầu.

Quy trình

Một cách là thay tham số fa bằng chỉ số cạnh vừa đi qua (mỗi cạnh có chỉ số riêng), tức là "không dùng cạnh vừa đi qua để cập nhật".

Cách khác là đặt một biến đánh dấu đã từng đi qua cha, lần sau gặp lại cha thì cập nhật bình thường.

Đoạn mã dưới đây tìm cầu trên đồ thị vô hướng có thể có cạnh lặp.

 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
int low[MAXN], dfn[MAXN], idx;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
  bool flag = false;
  father[u] = fa;
  low[u] = dfn[u] = ++idx;
  for (const auto &v : G[u]) {
    if (!dfn[v]) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > dfn[u]) {
        isbridge[v] = true;
        ++cnt_bridge;
      }
    } else {
      if (v != fa || flag)
        low[u] = min(low[u], dfn[v]);
      else
        flag = true;
    }
  }
}

Bài tập

Thuật toán Tarjan còn có nhiều ứng dụng khác, như tìm thành phần liên thông mạnh, thu gọn đồ thị, giải 2-SAT, v.v.

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Ir1d, sshwy, GavinZhengOI, Planet6174, ouuan, Marcythm, ylxmf2005, 0xis-cn
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply