Khớp, cầu và thành phần liên thông mạnh

Mức độ: Chuyên sâu

Một mạng đường bộ: con đường nào mà hỏng thì có hai nơi mất liên lạc? Ngã tư nào mà tắc thì mạng bị chia cắt? Con đường như vậy gọi là cầu, ngã tư như vậy gọi là khớp. Thử bỏ từng cạnh rồi kiểm tra liên thông mất m × (n + m) bước. Một lần DFS duy nhất tìm được tất cả.

Thời điểm thăm và giá trị low

Chạy DFS, ghi tin[u] là thứ tự u được thăm lần đầu (0, 1, 2, …). Các cạnh DFS đi theo tạo thành cây DFS; các cạnh còn lại nối một đỉnh với một tổ tiên của nó trên cây (gọi là cạnh ngược).

low[u] là tin nhỏ nhất mà từ cây con của u đi tới được bằng cách dùng một cạnh ngược (hoặc tin[u] nếu không có). Tính khi DFS quay lui:

low[u] = min(tin[u], tin[w] qua cạnh ngược u - w, low[v] qua các con v)

• Cạnh cây (u, v) là cầu khi low[v] > tin[u]: từ cây con của v không có đường nào vòng lên u hoặc cao hơn, bỏ cạnh này thì cây con của v bị tách ra.
• Đỉnh u (không phải gốc) là khớp khi có một con v với low[v] ≥ tin[u]: cây con của v không vòng được lên trên u, bỏ u thì nó bị tách ra. Gốc DFS là khớp khi có từ hai con trở lên trên cây DFS.

Đồ thị 1-2, 2-3, 3-1, 3-4, 4-5 (DFS từ 1 theo thứ tự 1, 2, 3, 4, 5):

Đỉnh	tin	low	Giải thích
1	0	0
2	1	0
3	2	0	cạnh ngược 3 - 1
4	3	3	không có cạnh ngược
5	4	4

Cạnh 3-4 là cầu (low[4] = 3 > tin[3] = 2), cạnh 4-5 là cầu. Đỉnh 3 là khớp (con 4 có low 3 ≥ tin 2), đỉnh 4 là khớp (con 5 có low 4 ≥ 3).

Python

import sys
du_lieu = sys.stdin.read().split()
n, m = int(du_lieu[0]), int(du_lieu[1])
ke = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = int(du_lieu[2 + 2 * i]), int(du_lieu[3 + 2 * i])
    ke[u].append((v, i))                 # lưu cả số hiệu cạnh để phân biệt cạnh lặp
    ke[v].append((u, i))
tin = [-1] * (n + 1)
low = [0] * (n + 1)
dem = 0
cau = []
for goc in range(1, n + 1):
    if tin[goc] >= 0:
        continue
    tin[goc] = low[goc] = dem
    dem += 1
    ngan_xep = [(goc, -1, 0)]            # (đỉnh, cạnh đi vào, vị trí đang duyệt trong ke)
    while ngan_xep:
        u, canh_vao, k = ngan_xep[-1]
        if k < len(ke[u]):
            ngan_xep[-1] = (u, canh_vao, k + 1)
            v, id_canh = ke[u][k]
            if id_canh == canh_vao:
                continue
            if tin[v] < 0:               # cạnh cây: đi xuống v
                tin[v] = low[v] = dem
                dem += 1
                ngan_xep.append((v, id_canh, 0))
            else:                        # cạnh ngược
                low[u] = min(low[u], tin[v])
        else:                            # xong u, quay lui về cha
            ngan_xep.pop()
            if ngan_xep:
                p = ngan_xep[-1][0]
                low[p] = min(low[p], low[u])
                if low[u] > tin[p]:
                    cau.append((min(p, u), max(p, u)))
print(len(cau))

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, dem = 0;
vector<vector<pair<int, int>>> ke;    // (đỉnh kề, số hiệu cạnh)
vector<int> tin, low;
int soCau = 0;

void dfs(int u, int canhVao) {
    tin[u] = low[u] = dem++;
    for (auto [v, id] : ke[u]) {
        if (id == canhVao) continue;
        if (tin[v] < 0) {                 // cạnh cây
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) soCau++;
        } else {                          // cạnh ngược
            low[u] = min(low[u], tin[v]);
        }
    }
}

int main() {
    cin >> n >> m;
    ke.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back({v, i});
        ke[v].push_back({u, i});
    }
    tin.assign(n + 1, -1);
    low.assign(n + 1, 0);
    for (int u = 1; u <= n; u++)
        if (tin[u] < 0) dfs(u, -1);
    cout << soCau << "\n";
    return 0;
}

Lưu ý: bỏ qua đúng cạnh vừa đi xuống (theo số hiệu cạnh), không bỏ qua mọi cạnh tới cha. Nếu có hai cạnh song song giữa u và cha thì cạnh thứ hai là cạnh ngược, và cạnh cây không còn là cầu.

Thành phần liên thông mạnh

Trong đồ thị có hướng, hai đỉnh liên thông mạnh khi đi được từ đỉnh này tới đỉnh kia và ngược lại. Các đỉnh chia thành các thành phần liên thông mạnh (SCC). Gộp mỗi thành phần thành một đỉnh thì được đồ thị nén, luôn là một DAG: nếu có chu trình giữa hai thành phần thì chúng đã phải là một.

Thuật toán Kosaraju gồm hai lần DFS:

1. DFS trên đồ thị gốc, ghi các đỉnh theo thứ tự hoàn thành (lúc quay lui).
2. Đảo chiều mọi cạnh. Đi các đỉnh theo thứ tự hoàn thành ngược lại (đỉnh xong sau cùng đi trước); mỗi đỉnh chưa thăm bắt đầu một lần duyệt trên đồ thị đảo, các đỉnh duyệt được là đúng một thành phần.

Ý tưởng: đỉnh xong sau cùng nằm trong một thành phần “nguồn” của đồ thị nén. Trên đồ thị đảo, thành phần đó thành “đích”, duyệt từ nó không đi lọt sang thành phần khác.

Luyện tập

Gồm 12 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Cầu

Bài 1. Đếm số cầu

Đồ thị vô hướng n đỉnh, m cạnh (có thể có nhiều cạnh nối cùng hai đỉnh, không có cạnh nối một đỉnh với chính nó). Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra số cầu: số cạnh mà bỏ đi thì số thành phần liên thông tăng lên.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 3 4 4 5	2

Kiểm tra: nhập

8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 4
7 8
7 8

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Liệt kê các cầu

Như bài 1. In ra số cầu trên dòng đầu, rồi mỗi dòng một cầu dạng u v với u nhỏ hơn v, các cầu xếp tăng dần theo u rồi theo v.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 3 4 4 5	2 3 4 4 5

Kiểm tra: nhập

8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 4
7 8
6 7

Xem đáp số

3
3 4
6 7
7 8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Cắt một con đường

Mạng đường liên thông gồm n thành phố, m con đường hai chiều. Phải đóng đúng một con đường để sửa. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, n - 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. Gọi số cặp thành phố (không kể thứ tự) còn đi được tới nhau sau khi đóng là P. In ra P nhỏ nhất có thể (chọn con đường để đóng sao cho mạng bị chia cắt nhiều nhất).

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 3 4 4 5	4

Kiểm tra: nhập

7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 4
6 7

Xem đáp số

9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Khớp

Bài 4. Đếm số khớp

Đồ thị vô hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (u khác v). In ra số khớp: số đỉnh mà bỏ đi (cùng các cạnh nối với nó) thì số thành phần liên thông của các đỉnh còn lại tăng lên.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 3 4 4 5	2

Kiểm tra: nhập

9 11
1 2
2 3
3 1
3 4
4 5
5 3
5 6
6 7
7 8
8 6
8 9

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Liệt kê các khớp

Như bài 4. In ra các khớp theo thứ tự tăng dần trên một dòng, hoặc -1 nếu không có khớp nào.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 3 4 4 5	3 4

Kiểm tra: nhập

9 11
1 2
2 3
3 1
3 4
4 5
5 3
5 6
6 7
7 8
8 6
8 9

Xem đáp số

3 5 6 8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Bỏ một ngã tư

Đồ thị vô hướng liên thông n đỉnh, m cạnh. Dòng đầu có n, m (2 ≤ n ≤ 10⁵, n - 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (u khác v). Bỏ một đỉnh (cùng các cạnh của nó). In ra số thành phần liên thông nhiều nhất của các đỉnh còn lại.

Ví dụ:

Nhập	In ra
5 4 1 2 1 3 1 4 4 5	3

Kiểm tra: nhập

8 9
1 2
2 3
3 1
3 4
4 5
4 6
6 7
7 8
8 6

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Thành phần liên thông mạnh

Bài 7. Có liên thông mạnh không

Đồ thị có hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (cạnh u → v). In ra YES nếu từ mọi đỉnh đi được tới mọi đỉnh khác, ngược lại NO.

Ví dụ:

Nhập	In ra
4 5 1 2 2 3 3 1 3 4 4 1	YES

Kiểm tra: nhập

5 6
1 2
2 3
3 1
3 4
4 5
5 4

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đếm thành phần liên thông mạnh

Đồ thị có hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra số thành phần liên thông mạnh và số đỉnh của thành phần lớn nhất.

Ví dụ:

Nhập	In ra
6 7 1 2 2 3 3 1 3 4 4 5 5 4 5 6	3 3

Kiểm tra: nhập

8 10
1 2
2 1
2 3
3 4
4 5
5 3
6 7
7 8
8 6
5 6

Xem đáp số

3 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hỏi hai đỉnh có cùng thành phần

Đồ thị có hướng n đỉnh, m cạnh và q câu hỏi. Dòng đầu có n, m, q (1 ≤ n, q ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh, q dòng sau mỗi dòng có a, b. Với mỗi câu hỏi, in ra YES nếu từ a đi tới được b và từ b đi tới được a, ngược lại NO.

Ví dụ:

Nhập	In ra
6 7 3 1 2 2 3 3 1 3 4 4 5 5 4 5 6 1 3 3 4 5 4	YES NO YES

Kiểm tra: nhập

8 10 4
1 2
2 1
2 3
3 4
4 5
5 3
6 7
7 8
8 6
5 6
1 2
3 5
5 7
6 8

Xem đáp số

YES
YES
NO
YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Thêm ít cạnh nhất để liên thông mạnh

Đồ thị có hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh. In ra số cạnh có hướng ít nhất cần thêm để đồ thị liên thông mạnh.

Ví dụ:

Nhập	In ra
4 3 1 2 2 3 2 4	2

Kiểm tra: nhập

8 10
1 2
2 1
2 3
3 4
4 5
5 3
6 7
7 8
8 6
5 6

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Đồ thị nén

Bài 11. Nhặt nhiều xu nhất

Đồ thị có hướng n phòng, m cửa một chiều; phòng i có c_i đồng xu. Bắt đầu ở phòng bất kỳ, đi qua các cửa (được đi lại phòng cũ), mỗi phòng nhặt xu một lần. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), dòng thứ hai có n số c_i (0 ≤ c_i ≤ 10⁹), m dòng sau mỗi dòng có u, v. In ra số xu nhiều nhất nhặt được.

Ví dụ:

Nhập	In ra
4 4 4 5 2 7 1 2 2 1 1 3 2 4	16

Kiểm tra: nhập

7 9
3 1 4 1 5 9 2
1 2
2 3
3 1
3 4
4 5
5 4
2 6
6 7
7 6

Xem đáp số

19

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Thứ tự tô-pô của các thành phần

Đồ thị có hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh. Đánh số các thành phần liên thông mạnh từ 1 sao cho mọi cạnh nối hai thành phần khác nhau đều đi từ thành phần số nhỏ tới thành phần số lớn; khi có nhiều cách, thành phần chứa đỉnh có số nhỏ nhất trong số các thành phần có thể đứng trước được đánh số trước. In ra số hiệu thành phần của các đỉnh 1, 2, …, n.

Ví dụ:

Nhập	In ra
6 7 1 2 2 3 3 1 3 4 4 5 5 4 5 6	1 1 1 2 2 3

Kiểm tra: nhập

8 9
2 1
1 2
3 4
4 3
5 3
6 7
7 6
8 5
2 6

Xem đáp số

1 1 5 5 4 2 2 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.