Đồ thị hai phía và ghép cặp

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

Đồ thị hai phía là đồ thị chia được các đỉnh thành hai nhóm, sao cho mọi cạnh nối một đỉnh nhóm này với một đỉnh nhóm kia (không có cạnh trong cùng một nhóm). Ví dụ: các bạn nam và các bạn nữ với cạnh là “nhảy cùng nhau được”; các công nhân và các công việc với cạnh là “làm được việc đó”; các ô đen và ô trắng của bàn cờ với cạnh là “hai ô kề nhau”.

Kiểm tra đồ thị hai phía: tô hai màu

Tô mỗi đỉnh một trong hai màu sao cho hai đầu của mọi cạnh khác màu. Đi BFS từ một đỉnh tô màu 0: mọi đỉnh kề phải màu 1, mọi đỉnh kề của chúng phải màu 0… Màu của từng đỉnh bị ép hoàn toàn khi đã chọn màu đỉnh đầu, nên nếu gặp một cạnh có hai đầu cùng màu thì không có cách tô nào.

Gặp cạnh hai đầu cùng màu nghĩa là có chu trình độ dài lẻ: đi quanh chu trình, màu đổi ở mỗi cạnh, đi một số lẻ cạnh mà quay về đúng màu ban đầu là vô lý. Vậy: đồ thị là hai phía khi và chỉ khi không có chu trình lẻ. Tam giác (chu trình dài 3) không hai phía; hình vuông (dài 4) thì hai phía.

Python

import sys
from collections import deque
d = sys.stdin.read().split()
n, m = int(d[0]), int(d[1])
ke = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = int(d[2 + 2 * i]), int(d[3 + 2 * i])
    ke[u].append(v)
    ke[v].append(u)
mau = [-1] * (n + 1)
hai_phia = True
for goc in range(1, n + 1):          # đồ thị có thể có nhiều thành phần
    if mau[goc] != -1:
        continue
    mau[goc] = 0
    hang_doi = deque([goc])
    while hang_doi:
        u = hang_doi.popleft()
        for v in ke[u]:
            if mau[v] == -1:
                mau[v] = 1 - mau[u]
                hang_doi.append(v)
            elif mau[v] == mau[u]:
                hai_phia = False
print("YES" if hai_phia else "NO")

C++

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> ke(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    vector<int> mau(n + 1, -1);
    bool haiPhia = true;
    for (int goc = 1; goc <= n; goc++) {
        if (mau[goc] != -1) continue;
        mau[goc] = 0;
        queue<int> hangDoi;
        hangDoi.push(goc);
        while (!hangDoi.empty()) {
            int u = hangDoi.front();
            hangDoi.pop();
            for (int v : ke[u]) {
                if (mau[v] == -1) {
                    mau[v] = 1 - mau[u];
                    hangDoi.push(v);
                } else if (mau[v] == mau[u]) haiPhia = false;
            }
        }
    }
    cout << (haiPhia ? "YES" : "NO") << "\n";
    return 0;
}

Ghép cặp lớn nhất

Một ghép cặp là một tập cạnh không có hai cạnh nào chung đỉnh (mỗi người ghép với nhiều nhất một người). Bài toán: chọn được nhiều cặp nhất là bao nhiêu? Ví dụ 3 công nhân A, B, C và 3 việc 1, 2, 3; A làm được việc 1, 2; B chỉ làm được việc 1; C làm được việc 2, 3.

Ghép tham lam A với việc 1 thì B không còn việc. Nhưng không cần làm lại từ đầu: B muốn việc 1, việc 1 đang của A, A chuyển sang việc 2 được (việc 2 còn trống) thì B lấy việc 1. Dãy B → 1 → A → 2 gọi là đường tăng: bắt đầu ở một người chưa ghép, kết thúc ở một việc còn trống, xen kẽ cạnh chưa ghép và cạnh đang ghép. Đổi trạng thái mọi cạnh trên đường tăng làm số cặp tăng 1.

Định lý Berge: ghép cặp là lớn nhất khi và chỉ khi không còn đường tăng. Vì vậy thuật toán chỉ cần lần lượt với mỗi người bên trái, tìm một đường tăng bắt đầu từ người đó bằng DFS. Đây là thuật toán Kuhn.

thu(u): thử tìm việc cho u. Với mỗi việc v mà u làm được (và chưa xét trong lần thử này): nếu v trống, hoặc người đang giữ v tìm được việc khác (gọi thu đệ quy), thì giao v cho u.

Lần thử	Diễn biến	Ghép cặp
A	việc 1 trống, giao cho A	A-1
B	việc 1 của A; thử A: việc 1 đã xét, việc 2 trống, A sang việc 2	A-2, B-1
C	việc 2 của A; thử A: việc 1 của B, thử B: không còn việc; A hết cách. C thử việc 3 trống	A-2, B-1, C-3

Được 3 cặp.

Python

import sys
sys.setrecursionlimit(10000)
d = sys.stdin.read().split()
n, k, m = int(d[0]), int(d[1]), int(d[2])      # n người bên trái, k việc bên phải
ke = [[] for _ in range(n + 1)]
for i in range(m):
    ke[int(d[3 + 2 * i])].append(int(d[4 + 2 * i]))
nguoi_giu = [0] * (k + 1)                      # 0 là việc còn trống

def thu(u, da_xet):
    for v in ke[u]:
        if not da_xet[v]:
            da_xet[v] = True
            if nguoi_giu[v] == 0 or thu(nguoi_giu[v], da_xet):
                nguoi_giu[v] = u
                return True
    return False

so_cap = sum(1 for u in range(1, n + 1) if thu(u, [False] * (k + 1)))
print(so_cap)

C++

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

int n, k, m;
vector<vector<int>> ke;
vector<int> nguoiGiu;
vector<bool> daXet;

bool thu(int u) {
    for (int v : ke[u])
        if (!daXet[v]) {
            daXet[v] = true;
            if (nguoiGiu[v] == 0 || thu(nguoiGiu[v])) {
                nguoiGiu[v] = u;
                return true;
            }
        }
    return false;
}

int main() {
    cin >> n >> k >> m;
    ke.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
    }
    nguoiGiu.assign(k + 1, 0);
    int soCap = 0;
    for (int u = 1; u <= n; u++) {
        daXet.assign(k + 1, false);
        if (thu(u)) soCap++;
    }
    cout << soCap << "\n";
    return 0;
}

Mỗi lần thử duyệt mỗi cạnh nhiều nhất một lần (nhờ da_xet), nên tổng số bước khoảng n × (n + m). Với n vài trăm đến một nghìn là đủ nhanh.

Lưu ý: mảng da_xet phải làm mới cho mỗi người u, nhưng giữ nguyên trong suốt các lời gọi đệ quy của cùng một lần thử. Nếu không đánh dấu, DFS có thể chạy vòng tròn giữa hai người cùng muốn một việc.

Định lý König và các bài liên quan

Trên đồ thị hai phía, nhiều bài nghe rất khác nhau lại có đáp số tính từ ghép cặp lớn nhất (gọi là M):

Bài toán	Đáp số
phủ đỉnh ít nhất: chọn ít đỉnh nhất để mọi cạnh có ít nhất một đầu được chọn	M (định lý König)
tập độc lập lớn nhất: chọn nhiều đỉnh nhất không có hai đỉnh nào kề nhau	số đỉnh - M
phủ đường đi ít nhất trên DAG: chia các đỉnh thành ít đường đi rời nhau nhất	số đỉnh - M (trên đồ thị tách đôi mỗi đỉnh)

Vì sao phủ đỉnh cần ít nhất M đỉnh: M cạnh của ghép cặp không chung đầu, mỗi cạnh cần một đỉnh riêng để phủ. Định lý König nói M đỉnh là đủ. Tập độc lập là phần bù của một phủ đỉnh (bỏ các đỉnh phủ đi thì không còn cạnh nào), nên tập độc lập lớn nhất = số đỉnh - phủ đỉnh nhỏ nhất.

Dấu hiệu nhận ra: bài có hai loại đối tượng (hàng và cột, ô đen và ô trắng, người và việc), và mỗi đối tượng được dùng nhiều nhất một lần.

Luyện tập

Gồm 12 bài, chia thành 3 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. Tô hai màu

Bài 1. Có phải đồ thị hai phía

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 ≠ v): một cạnh vô hướng. In ra YES nếu đồ thị là đồ thị hai phía, ngược lại in ra NO.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

NO

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

Bài 2. Chia hai nhóm

Dữ liệu như bài 1: n bạn, mỗi cạnh là một cặp bạn không muốn ở cùng nhóm. Chia các bạn thành nhóm A và nhóm B (một nhóm có thể không có ai) sao cho không cặp nào ở cùng nhóm. In ra số bạn nhiều nhất có thể có trong nhóm A, hoặc -1 nếu không chia được.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

6

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

Bài 3. Đếm số cách tô

Dữ liệu như bài 1. In ra số cách tô mỗi đỉnh một trong hai màu đen, trắng sao cho hai đầu mỗi cạnh khác màu, lấy phần dư khi chia cho 10⁹ + 7.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

16

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

Bài 4. Thêm cạnh mà vẫn hai phía

Dòng đầu có n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v: một cạnh. Đồ thị đã cho là hai phía, không có hai cạnh nào nối cùng một cặp đỉnh. Đếm số cặp đỉnh u < v chưa có cạnh mà thêm cạnh u - v vào thì đồ thị vẫn là hai phía.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

19

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

Nhóm 2. Ghép cặp lớn nhất

Bài 5. Phân công việc

Dòng đầu có n, k, m (1 ≤ n, k ≤ 500, 0 ≤ m ≤ 2 × 10⁴): n công nhân, k công việc. m dòng sau mỗi dòng có u, v: công nhân u làm được việc v. Mỗi công nhân làm nhiều nhất một việc, mỗi việc do nhiều nhất một công nhân làm. In ra số việc nhiều nhất được giao.

Ví dụ:

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

Kiểm tra: nhập

5 5 9
1 1
1 2
2 1
3 2
3 3
4 3
5 3
5 4
4 5

Xem đáp số

5

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

Bài 6. Ghép đôi nhảy

Dòng đầu có n, k, D (1 ≤ n, k ≤ 500, 0 ≤ D ≤ 10⁹), dòng thứ hai có chiều cao n bạn nam, dòng thứ ba có chiều cao k bạn nữ (mỗi số từ 1 đến 10⁹). Một bạn nam và một bạn nữ nhảy cùng được nếu chiều cao chênh nhau không quá D. In ra số đôi nhiều nhất.

Ví dụ:

Nhập	In ra
3 3 5 160 170 180 158 176 190	2

Kiểm tra: nhập

6 5 4
150 162 155 170 168 181
158 166 151 175 180

Xem đáp số

4

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

Bài 7. Đặt quân xe

Dòng đầu có h, w (1 ≤ h, w ≤ 300), h dòng sau mỗi dòng có w ký tự: . là ô đặt được, # là ô không đặt được. Đặt nhiều quân xe nhất vào các ô . sao cho không có hai quân nào cùng hàng hoặc cùng cột. In ra số quân đó.

Ví dụ:

Nhập	In ra
3 3 .#. #.. .##	3

Kiểm tra: nhập

4 5
..#..
#####
.#...
..#.#

Xem đáp số

3

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

Bài 8. Lát domino

Dòng đầu có h, w (1 ≤ h, w ≤ 50), h dòng sau mỗi dòng có w ký tự: . là ô trống, # là ô bị chắn. Mỗi quân domino phủ hai ô trống kề cạnh, các quân không chồng lên nhau. In ra số quân domino nhiều nhất đặt được.

Ví dụ:

Nhập	In ra
3 3 ... .#. ...	4

Kiểm tra: nhập

4 5
..#..
.....
#..#.
...##

Xem đáp số

7

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

Nhóm 3. Định lý König

Bài 9. Ít đỉnh phủ mọi cạnh

Dữ liệu như bài 5 (n đỉnh trái, k đỉnh phải, m cạnh). Chọn ít đỉnh nhất (ở cả hai bên) sao cho mọi cạnh có ít nhất một đầu được chọn. In ra số đỉnh đó.

Ví dụ:

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

Kiểm tra: nhập

4 4 7
1 1
1 2
2 2
3 2
3 3
4 3
4 4

Xem đáp số

4

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

Bài 10. Bắn bia

Dòng đầu có h, w (1 ≤ h, w ≤ 300), h dòng sau mỗi dòng có w ký tự: x là ô có bia, . là ô trống. Mỗi phát súng phá hết bia trên một hàng hoặc một cột tùy chọn. In ra số phát ít nhất để phá hết bia.

Ví dụ:

Nhập	In ra
3 4 x..x .x.. .x..	2

Kiểm tra: nhập

4 5
x.x..
..x..
x.x.x
....x

Xem đáp số

3

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

Bài 11. Chọn ô không kề nhau

Dữ liệu như bài 8. Chọn nhiều ô trống nhất sao cho không có hai ô được chọn nào kề cạnh nhau. In ra số ô đó.

Ví dụ:

Nhập	In ra
3 3 ... .#. ...	4

Kiểm tra: nhập

4 5
..#..
.....
#..#.
...##

Xem đáp số

8

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

Bài 12. Ít xe nhất

Dòng đầu có n, m (1 ≤ n ≤ 500, 0 ≤ m ≤ 2 × 10⁴), m dòng sau mỗi dòng có u, v (u < v): một xe làm xong việc u thì làm tiếp được việc v. Mỗi xe làm lần lượt một dãy việc nối tiếp nhau như vậy. In ra số xe ít nhất để làm hết n việc, mỗi việc do đúng một xe làm.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

2

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.