Bài 19.4. Bài toán ghép cặp tối đa trên đồ thị hai phía

Chào mừng các bạn quay trở lại với series "Cấu trúc dữ liệu và Giải thuật"! Hôm nay, chúng ta sẽ cùng nhau khám phá một bài toán vô cùng thú vị và có nhiều ứng dụng thực tế: Bài toán ghép cặp tối đa trên đồ thị hai phía (Maximum Bipartite Matching). Đừng để cái tên "lý thuyết đồ thị" làm bạn e ngại, đằng sau nó là những ý tưởng tuyệt vời để giải quyết nhiều vấn đề từ việc phân công công việc, ghép đôi hẹn hò, cho đến lập lịch thi đấu!

Hãy tưởng tượng bạn là người quản lý tại một công ty. Bạn có một danh sách các dự án cần hoàn thành và một danh sách các nhân viên. Mỗi nhân viên lại có kỹ năng phù hợp với một hoặc nhiều dự án khác nhau. Mục tiêu của bạn là phân công càng nhiều dự án cho nhân viên càng tốt, với điều kiện mỗi dự án chỉ được giao cho một nhân viên và mỗi nhân viên chỉ nhận một dự án duy nhất. Đây chính là một ví dụ điển hình của bài toán ghép cặp trên đồ thị hai phía!

Đồ thị Hai Phía là gì?

Trước khi đi sâu vào bài toán ghép cặp, chúng ta cần hiểu rõ về loại đồ thị mà chúng ta đang làm việc: đồ thị hai phía (Bipartite Graph).

Một đồ thị được gọi là hai phía nếu tập hợp các đỉnh của nó có thể được chia thành hai tập hợp không giao nhau (gọi là U và V) sao cho mọi cạnh trong đồ thị đều nối một đỉnh từ tập U với một đỉnh từ tập V. Quan trọng là, không có cạnh nào nối hai đỉnh cùng nằm trong tập U, và cũng không có cạnh nào nối hai đỉnh cùng nằm trong tập V.

Tưởng tượng tập U là các nhân viên và tập V là các dự án. Một cạnh nối nhân viên u thuộc U và dự án v thuộc V chỉ ra rằng nhân viên u có thể làm dự án v. Rõ ràng, một nhân viên không thể "nối" với một nhân viên khác (đều thuộc tập U), và một dự án cũng không thể "nối" với một dự án khác (đều thuộc tập V) trong ngữ cảnh này.

Cách đơn giản để kiểm tra một đồ thị có phải là hai phía hay không là thử tô màu 2 màu. Nếu bạn có thể tô màu các đỉnh bằng hai màu (ví dụ: đen và trắng) sao cho mọi cạnh đều nối một đỉnh màu đen với một đỉnh màu trắng, thì đồ thị đó là hai phía.

Ghép Cặp (Matching) là gì?

Trong một đồ thị (bất kỳ, không chỉ hai phía), một ghép cặp (Matching) là một tập hợp các cạnh sao cho không có hai cạnh nào trong tập hợp này có chung một đỉnh.

Trở lại ví dụ nhân viên - dự án: một ghép cặp là một tập hợp các cặp (nhân viên, dự án) đã được phân công, sao cho không có nhân viên nào được giao hai dự án và không có dự án nào được giao cho hai nhân viên.

Bài toán ghép cặp tối đa (Maximum Matching) là tìm một ghép cặp chứa số lượng cạnh lớn nhất có thể. Mục tiêu của chúng ta chính là tìm cách phân công được nhiều dự án nhất cho nhân viên thỏa mãn các điều kiện.

Đối với đồ thị hai phía, bài toán ghép cặp tối đa có những giải thuật rất hiệu quả, nổi bật nhất là giải thuật dựa trên việc tìm đường tăng (Augmenting Path).

Sức Mạnh của Đường Tăng (Augmenting Path)

Ý tưởng chính đằng sau nhiều giải thuật tìm ghép cặp tối đa trên đồ thị hai phía là sử dụng khái niệm đường tăng.

Một đường tăng đối với một ghép cặp hiện tại M là một đường đi đơn giản (không lặp lại đỉnh) trong đồ thị, thỏa mãn hai điều kiện:

Nó bắt đầu và kết thúc tại các đỉnh chưa được ghép cặp (unmatched vertices).
Các cạnh trên đường đi này xen kẽ giữa các cạnh không thuộc M và các cạnh thuộc M.

Ví dụ: Giả sử bạn có đường đi u1 - v1 - u2 - v2 - u3, trong đó u1, u2, u3 thuộc U và v1, v2 thuộc V.

Nếu cạnh (u1, v1) không thuộc ghép cặp M.
Nếu cạnh (v1, u2) (hoặc (u2, v1)) thuộc ghép cặp M (tức là v1 đang ghép với u2).
Nếu cạnh (u2, v2) không thuộc ghép cặp M.
Nếu cạnh (v2, u3) (hoặc (u3, v2)) thuộc ghép cặp M (tức là v2 đang ghép với u3).
Và giả sử u1 và u3 hiện chưa được ghép cặp.

Thì đường đi u1 - v1 - u2 - v2 - u3 là một đường tăng.

Tại sao đường tăng lại quan trọng? Bởi vì nếu ta tìm được một đường tăng, ta có thể cải thiện ghép cặp hiện tại bằng cách "lật" trạng thái của các cạnh trên đường đi đó:

Các cạnh không thuộc M trên đường đi sẽ được thêm vào M.
Các cạnh thuộc M trên đường đi sẽ bị loại bỏ khỏi M.

Kết quả của thao tác "lật" này sẽ là một ghép cặp mới có số lượng cạnh lớn hơn 1 so với ghép cặp cũ!

Ví dụ trên:

Loại bỏ (v1, u2) và (v2, u3) khỏi M.
Thêm (u1, v1), (u2, v2) vào M.
Đỉnh u1 giờ ghép với v1. Đỉnh u3 giờ ghép với v2. Đỉnh u2 (trước ghép với v1) giờ ghép với v2. À khoan! Ví dụ này hơi rối. Hãy xem xét một đường tăng đơn giản hơn trên đồ thị hai phía U-V: u1 - v1 - u2 - v2, nơi u1 chưa ghép, v2 chưa ghép, (u1, v1) không ghép, (v1, u2) ghép, (u2, v2) không ghép.
- Trước: u1 chưa ghép, v1 ghép với u2, v2 chưa ghép.
- Lật: Bỏ (v1, u2), thêm (u1, v1), thêm (u2, v2).
- Sau: u1 ghép với v1, u2 ghép với v2. Số lượng ghép cặp tăng từ 1 lên 2. Cả u1 và u2 (từ U), v1 và v2 (từ V) đều được ghép.

Định lý quan trọng (Konig's Theorem liên quan): Số lượng cạnh trong một ghép cặp tối đa bằng kích thước của tập đỉnh phủ tối thiểu (minimum vertex cover). Quan trọng hơn cho giải thuật của chúng ta: Một ghép cặp M là tối đa khi và chỉ khi không tồn tại đường tăng nào đối với M.

Điều này cho chúng ta một giải thuật: Bắt đầu với một ghép cặp rỗng (hoặc bất kỳ). Lặp đi lặp lại việc tìm một đường tăng và cải thiện ghép cặp cho đến khi không thể tìm thấy đường tăng nào nữa.

Giải thuật tìm Ghép Cặp Tối Đa dùng DFS

Một trong những cách phổ biến và dễ cài đặt nhất để tìm đường tăng là sử dụng thuật toán tìm kiếm theo chiều sâu (DFS).

Chúng ta sẽ xét các đỉnh ở một phía của đồ thị hai phía, ví dụ tập U. Đối với mỗi đỉnh u trong U hiện chưa được ghép cặp, ta sẽ thử tìm một đường tăng bắt đầu từ u.

Hàm DFS sẽ có dạng bool dfs(int u) trả về true nếu tìm thấy và sử dụng được một đường tăng bắt đầu từ u, và false nếu không tìm được.

Để tìm đường tăng bắt đầu từ u (một đỉnh chưa ghép ở U):

Duyệt qua tất cả các đỉnh v thuộc V mà có cạnh nối với u.
Đối với mỗi v:
- Nếu v chưa được thăm trong lần DFS này (để tránh chu trình hoặc thăm lại không cần thiết trong một lần tìm đường tăng): đánh dấu v đã thăm.
- Kiểm tra trạng thái của v:
  - Nếu v hiện chưa được ghép cặp với bất kỳ đỉnh nào trong U (tức là match[v] == -1), ta đã tìm thấy một đường tăng đơn giản: u -> v. Ta ghép u với v (match[v] = u), và trả về true (tìm thấy đường tăng).
  - Nếu v hiện đang được ghép cặp với một đỉnh khác u_prime trong U (match[v] = u_prime), ta thử xem liệu u_prime có thể tìm được một "đối tác" mới hay không bằng cách gọi đệ quy dfs(u_prime). Nếu dfs(u_prime) trả về true (nghĩa là u_prime tìm được đường tăng và ghép cặp với đỉnh khác), thì ta có thể "cướp" v cho u. Ta ghép u với v (match[v] = u), và trả về true.
Nếu duyệt qua tất cả các đỉnh v kề với u mà không tìm được cách ghép u (hoặc không thể "giải phóng" đối tác hiện tại của v), thì không có đường tăng nào bắt đầu từ u qua các đỉnh v đã xem xét trong lần DFS này. Hàm trả về false.

Quá trình chính sẽ là:

Khởi tạo mảng match (ví dụ: match[v] lưu đỉnh u mà v ghép với, khởi tạo tất cả bằng -1).
Lặp qua từng đỉnh u trong tập U.
Trước khi gọi dfs(u), reset mảng visited cho tập V (đánh dấu tất cả là chưa thăm). Điều này là cần thiết vì mảng visited chỉ có ý nghĩa trong phạm vi một lần gọi dfs để tìm một đường tăng duy nhất bắt đầu từ u. Khi bắt đầu tìm đường tăng từ đỉnh u khác, ta cần có cái nhìn "mới" về các đỉnh ở V.
Nếu dfs(u) trả về true, điều đó có nghĩa là ta đã tìm và sử dụng được một đường tăng, tăng số lượng ghép cặp lên 1.

Lặp lại bước 3 và 4 cho tất cả các đỉnh u trong U. Tổng số lần dfs(u) trả về true chính là kích thước của ghép cặp tối đa.

Ví dụ Minh Họa

Hãy xem xét một ví dụ nhỏ: Tập U = {1, 2, 3} (ví dụ: Nhân viên) Tập V = {1, 2, 3, 4} (ví dụ: Dự án) Các cạnh: (1, 1), (1, 2) (2, 1), (2, 3) (3, 3), (3, 4)

Đồ thị: U: 1 -- V: 1 | /| | / | 2 -/- 3 | | 4

Khởi tạo match cho V: match[1]=-1, match[2]=-1, match[3]=-1, match[4]=-1. Số ghép cặp = 0.

Xét đỉnh U=1: visited = {false, false, false, false} cho V={1,2,3,4}.
- Gọi dfs(1):
  - Duyệt kề của 1: v=1. v=1 chưa thăm. visited[1] = true.
  - match[1] là -1. Ghép 1 với 1: match[1] = 1. Trả về true.
- Số ghép cặp = 1. match = {1:1, 2:-1, 3:-1, 4:-1}. (Đỉnh 1 ở V ghép với đỉnh 1 ở U)
Xét đỉnh U=2: visited = {false, false, false, false}.
- Gọi dfs(2):
  - Duyệt kề của 2: v=1. v=1 chưa thăm. visited[1] = true.
  - match[1] là 1 (đang ghép với U=1). Thử dfs(match[1]) tức là dfs(1).
    - Gọi dfs(1) (đệ quy từ dfs(2)): visited là {true, false, false, false}.
    - Duyệt kề của 1: v=1. v=1 đã thăm. Bỏ qua.
    - Duyệt kề của 1: v=2. v=2 chưa thăm. visited[2] = true.
    - match[2] là -1. Ghép 1 với 2: match[2] = 1. Trả về true.
    - (Sau khi đệ quy dfs(1) trả về true, match = {1:-1, 2:1, 3:-1, 4:-1}. Nghĩa là U=1 giờ ghép với V=2, V=1 bị "giải phóng").
  - Quay lại dfs(2): vì dfs(1) trả về true, ta có thể "cướp" V=1. Ghép 2 với 1: match[1] = 2. Trả về true.
- Số ghép cặp = 2. match = {1:2, 2:1, 3:-1, 4:-1}. (V=1 ghép với U=2, V=2 ghép với U=1)
Xét đỉnh U=3: visited = {false, false, false, false}.
- Gọi dfs(3):
  - Duyệt kề của 3: v=3. v=3 chưa thăm. visited[3] = true.
  - match[3] là -1. Ghép 3 với 3: match[3] = 3. Trả về true.
- Số ghép cặp = 3. match = {1:2, 2:1, 3:3, 4:-1}. (V=1 ghép U=2, V=2 ghép U=1, V=3 ghép U=3)

Đã xét hết các đỉnh ở U. Ghép cặp tối đa tìm được có kích thước là 3.

Mã Nguồn C++ Minh Họa

Dưới đây là cài đặt giải thuật DFS tìm ghép cặp tối đa trên đồ thị hai phía bằng C++. Chúng ta giả sử các đỉnh của tập U được đánh số từ 1 đến N, và các đỉnh của tập V được đánh số từ 1 đến M.

#include <iostream>
#include <vector>
#include <numeric> // For std::iota, though not strictly necessary here, good practice for sequence generation if needed elsewhere
#include <algorithm> // For std::fill

using namespace std;

const int MAXN = 105; // Số đỉnh tối đa của tập U (hoặc V), điều chỉnh nếu cần
const int MAXM = 105; // Số đỉnh tối đa của tập V (hoặc U), điều chỉnh nếu cần

// adj[u] lưu danh sách các đỉnh v thuộc tập V mà u thuộc tập U có cạnh nối tới
vector<int> adj[MAXN];

// match[v] lưu đỉnh u thuộc tập U mà đỉnh v thuộc tập V đang được ghép cặp
// Giá trị -1 nghĩa là v chưa được ghép cặp
int match[MAXM];

// visited[v] đánh dấu đỉnh v thuộc tập V đã được thăm trong lần DFS hiện tại hay chưa
// Cần reset mảng này trước mỗi lần gọi dfs từ một đỉnh u mới
bool visited[MAXM];

// N: Số đỉnh của tập U
// M: Số đỉnh của tập V
int N, M;

// Hàm DFS để tìm đường tăng bắt đầu từ đỉnh u thuộc tập U
bool dfs(int u) {
    // Duyệt qua tất cả các đỉnh v thuộc tập V mà u có cạnh nối tới
    for (int v : adj[u]) {
        // Nếu v chưa được thăm trong lần DFS này
        if (!visited[v]) {
            visited[v] = true; // Đánh dấu v đã thăm

            // Nếu v chưa được ghép cặp (match[v] == -1) HOẶC
            // Nếu v đã được ghép cặp với đỉnh u_prime (match[v] == u_prime)
            // VÀ đỉnh u_prime có thể tìm được một đường tăng khác (dfs(u_prime) trả về true)
            // Điều kiện thứ hai này thể hiện việc u_prime "nhường" v lại cho u
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u; // Ghép đỉnh u với đỉnh v
                return true; // Tìm thấy và sử dụng được một đường tăng
            }
        }
    }

    // Không tìm được đỉnh v nào để ghép cặp với u trong lần DFS này
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Đọc input: N - số đỉnh tập U, M - số đỉnh tập V
    // K - số lượng cạnh
    int K;
    cin >> N >> M >> K;

    // Đọc K cạnh và xây dựng danh sách kề
    for (int i = 0; i < K; ++i) {
        int u, v;
        cin >> u >> v;
        // Giả sử u thuộc U (1..N), v thuộc V (1..M)
        adj[u].push_back(v);
    }

    // Khởi tạo mảng match: tất cả các đỉnh ở V đều chưa được ghép cặp
    fill(match + 1, match + M + 1, -1); // Sử dụng 1-based indexing cho match[1..M]

    int max_matching = 0;

    // Duyệt qua từng đỉnh u thuộc tập U (từ 1 đến N)
    for (int u = 1; u <= N; ++u) {
        // Reset mảng visited trước khi tìm đường tăng cho đỉnh u hiện tại
        // Mảng visited chỉ có ý nghĩa trong phạm vi 1 lần gọi dfs từ 1 đỉnh u
        fill(visited + 1, visited + M + 1, false); // Sử dụng 1-based indexing cho visited[1..M]

        // Nếu tìm được một đường tăng bắt đầu từ u
        if (dfs(u)) {
            max_matching++; // Tăng số lượng ghép cặp tối đa lên 1
        }
    }

    // In kết quả
    cout << max_matching << endl;

    return 0;
}

Giải Thích Mã Nguồn

Thư viện và Hằng số:
- iostream, vector, numeric, algorithm: Các thư viện cần thiết cho input/output, sử dụng vector, và các hàm tiện ích (như fill).
- MAXN, MAXM: Hằng số định nghĩa kích thước tối đa cho các tập đỉnh U và V. Cần điều chỉnh tùy theo giới hạn của bài toán. Chúng ta sử dụng 1-based indexing cho các đỉnh từ 1 đến N và 1 đến M.
- adj[MAXN]: Mảng các vector<int> biểu diễn danh sách kề. adj[u] chứa danh sách các đỉnh v thuộc tập V mà có cạnh nối với đỉnh u thuộc tập U.
- match[MAXM]: Mảng match[v] lưu trữ đỉnh u thuộc tập U mà đỉnh v thuộc tập V hiện đang được ghép cặp cùng. match[v] = -1 nếu v chưa được ghép. Kích thước MAXM vì ta lưu ghép cặp cho các đỉnh thuộc tập V.
- visited[MAXM]: Mảng boolean để đánh dấu các đỉnh thuộc tập V đã được thăm trong lần gọi hàm dfs hiện tại. Điều này ngăn chặn việc lặp vô hạn trong trường hợp có chu trình hoặc thăm lại không cần thiết. Kích thước MAXM vì ta kiểm tra visited cho các đỉnh thuộc V.
Biến N, M: Lưu số lượng đỉnh của tập U và tập V, được đọc từ input.
Hàm dfs(int u):
- Đây là trái tim của giải thuật, cố gắng tìm một đường tăng bắt đầu từ đỉnh u thuộc tập U.
- Nó duyệt qua tất cả các đỉnh v trong adj[u] (các đỉnh thuộc V kề với u).
- if (!visited[v]): Chỉ xử lý đỉnh v nếu nó chưa được thăm trong lần tìm đường tăng hiện tại.
- visited[v] = true;: Đánh dấu v đã thăm.
- if (match[v] == -1 || dfs(match[v])): Đây là logic chính của việc tìm đường tăng.
  - match[v] == -1: Nếu v chưa được ghép, ta đã tìm thấy một đường tăng đơn giản u -> v. Ta có thể ghép u với v.
  - dfs(match[v]): Nếu v đã được ghép với đỉnh u_prime = match[v], ta đệ quy gọi dfs(u_prime) để xem u_prime có thể tìm một đường tăng khác (tìm đối tác mới) hay không. Nếu u_prime thành công (hàm dfs(u_prime) trả về true), điều đó có nghĩa là u_prime đã nhường v lại và ghép với đỉnh khác. Khi đó, ta có thể ghép u với v.
- Nếu một trong hai điều kiện trên đúng, ta thực hiện match[v] = u; (ghép u với v) và trả về true báo hiệu tìm thấy đường tăng.
- Nếu duyệt hết các đỉnh kề mà không thể ghép u (hoặc "cướp" đối tác của chúng), hàm trả về false.
Hàm main():
- Đọc số đỉnh N, M và số cạnh K.
- Đọc K cạnh và xây dựng danh sách kề adj.
- fill(match + 1, match + M + 1, -1);: Khởi tạo mảng match với giá trị -1 cho tất cả các đỉnh từ 1 đến M của tập V. Sử dụng 1-based indexing nên bắt đầu từ match + 1.
- max_matching = 0;: Biến đếm số lượng ghép cặp tối đa.
- Vòng lặp for (int u = 1; u <= N; ++u): Lặp qua từng đỉnh u của tập U.
- fill(visited + 1, visited + M + 1, false);: Rất quan trọng! Reset mảng visited trước mỗi lần gọi dfs(u) cho một đỉnh u mới. Điều này đảm bảo rằng việc tìm đường tăng cho u không bị ảnh hưởng bởi trạng thái thăm của các lần tìm đường tăng trước đó từ các đỉnh u' khác.
- if (dfs(u)): Nếu dfs(u) trả về true (nghĩa là tìm và sử dụng được một đường tăng), tăng max_matching lên 1.
- Cuối cùng, in ra max_matching.

Độ phức tạp: Với mỗi đỉnh u trong tập U (có N đỉnh), ta gọi hàm dfs(u). Hàm dfs(u) có thể duyệt qua tất cả các cạnh kề với u, và trong trường hợp xấu nhất có thể đệ quy sâu tới M lần (kích thước tập V) và duyệt qua các cạnh tương ứng. Tổng cộng, độ phức tạp của giải thuật DFS này là O(N E), trong đó E là số lượng cạnh của đồ thị. Đối với đồ thị hai phía dày đặc (nhiều cạnh), E có thể lên tới N M, khi đó độ phức tạp là O(N N M) hoặc O(M N M) tùy cách cài đặt và kích thước N, M. Một cách ước lượng phổ biến là O(VE) hoặc O(V^3) trong trường hợp tổng quát, trong đó V là tổng số đỉnh (N+M). Mặc dù không nhanh bằng thuật toán Hopcroft-Karp (O(E sqrt(V))), thuật toán DFS này đủ nhanh cho nhiều bài toán và dễ hiểu hơn.

Bài tập ví dụ:

Hành trình vòng quanh II

Trong một dự án phát triển cơ sở hạ tầng, FullHouse Dev được giao nhiệm vụ thiết kế một hành trình vòng quanh giữa các thành phố. Họ cần tìm cách bắt đầu từ một thành phố, đi qua một hoặc nhiều thành phố khác, và cuối cùng quay trở lại thành phố xuất phát. Mỗi thành phố trung gian trên hành trình phải là duy nhất.

Bài toán

FullHouse Dev nhận được thông tin về \(n\) thành phố và \(m\) chuyến bay. Nhiệm vụ của họ là thiết kế một hành trình vòng quanh bắt đầu từ một thành phố, đi qua một hoặc nhiều thành phố khác, và cuối cùng quay trở lại thành phố xuất phát. Mỗi thành phố trung gian trên hành trình phải là duy nhất.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số từ 1 đến \(n\).
Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả các chuyến bay là chuyến bay một chiều từ một thành phố đến một thành phố khác.

OUTPUT FORMAT:

Đầu tiên in ra một số nguyên \(k\): số lượng thành phố trên hành trình. Sau đó in ra \(k\) thành phố theo thứ tự chúng sẽ được ghé thăm. Bạn có thể in ra bất kỳ giải pháp hợp lệ nào.
Nếu không có giải pháp, in ra "IMPOSSIBLE".

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq m \leq 2 \cdot 10^5\)
\(1 \leq a, b \leq n\)

Ví dụ

INPUT

OUTPUT

4
2 1 3 2

Giải thích

Trong ví dụ này, FullHouse Dev có thể bắt đầu từ thành phố 2, đi đến thành phố 1, sau đó đến thành phố 3, và quay trở lại thành phố 2. Vì vậy, đáp án là 4 với hành trình 2 1 3 2. Okay, đây là hướng dẫn giải bài toán "Hành trình vòng quanh II" sử dụng C++ mà không cung cấp code hoàn chỉnh.

Ý tưởng chính:

Bài toán yêu cầu tìm một chu trình đơn (simple cycle) trong đồ thị có hướng. Một chu trình đơn là một đường đi bắt đầu và kết thúc tại cùng một đỉnh, đi qua các đỉnh trung gian là duy nhất (không lặp lại đỉnh nào ngoại trừ đỉnh xuất phát/kết thúc).

Thuật toán hiệu quả để tìm chu trình trong đồ thị có hướng là sử dụng Depth First Search (DFS - Tìm kiếm theo chiều sâu).

Các bước thực hiện:

Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list) để lưu trữ đồ thị. Vì các chuyến bay là một chiều, danh sách kề sẽ lưu các cạnh đi ra từ mỗi thành phố.
- Sử dụng std::vector<int> adj[N] hoặc std::vector<std::vector<int>> adj(n + 1) trong C++.
Theo dõi trạng thái đỉnh trong DFS: Trong quá trình DFS trên đồ thị có hướng, cần theo dõi 3 trạng thái của mỗi đỉnh để phát hiện chu trình:
- UNVISITED (Chưa thăm): Đỉnh chưa bao giờ được ghé thăm trong quá trình DFS hiện tại.
- VISITING (Đang thăm / Trong stack đệ quy): Đỉnh hiện đang nằm trong đường đi từ đỉnh bắt đầu DFS đến đỉnh hiện tại.
- VISITED (Đã thăm xong): DFS đã hoàn thành việc thăm tất cả các đỉnh có thể từ đỉnh này.
- Sử dụng một mảng (ví dụ: int state[N]) để lưu trạng thái của từng đỉnh. Khởi tạo tất cả trạng thái là UNVISITED.
Thực hiện DFS:
- Duyệt qua tất cả các đỉnh từ 1 đến n. Nếu một đỉnh chưa được thăm (UNVISITED), bắt đầu một DFS mới từ đỉnh đó.
- Trong hàm DFS cho đỉnh u:
  - Đánh dấu trạng thái của u là VISITING.
  - Lưu lại đỉnh cha của u trong cây DFS hiện tại. Sử dụng một mảng parent[N].
  - Duyệt qua tất cả các đỉnh kề v của u:
    - Nếu v có trạng thái UNVISITED: Đây là một cạnh cây (tree edge). Đặt parent[v] = u và gọi đệ quy dfs(v). Nếu cuộc gọi đệ quy này tìm thấy một chu trình, dừng ngay lập tức và trả về (lan truyền việc tìm thấy chu trình lên các lớp đệ quy cao hơn).
    - Nếu v có trạng thái VISITING: Chu trình đã được phát hiện! Cạnh từ u đến v là một cạnh ngược (back edge) trỏ tới một đỉnh đang nằm trong stack đệ quy (tức là một tổ tiên của u). Chu trình là v -> ... -> parent[u] -> u -> v. Lưu lại đỉnh bắt đầu chu trình (v) và đỉnh kết thúc cạnh gây ra chu trình (u). Đặt cờ hiệu báo đã tìm thấy chu trình và dừng các cuộc gọi đệ quy tiếp theo.
    - Nếu v có trạng thái VISITED: Đây là một cạnh chéo hoặc cạnh tiến tới một nhánh đã hoàn thành. Không cần xử lý thêm.
  - Sau khi duyệt qua tất cả đỉnh kề của u mà không phát hiện chu trình từ u (hoặc chu trình đã được phát hiện và cờ hiệu được đặt), đánh dấu trạng thái của u là VISITED.
Xử lý khi tìm thấy chu trình:
- Khi phát hiện chu trình (trạng thái VISITING của đỉnh v khi đi từ u): Chu trình đi từ v, ngược theo các đỉnh cha trong mảng parent đến u, và cuối cùng là cạnh u -> v.
- Để xây dựng đường đi của chu trình:
  - Bắt đầu từ đỉnh u (cycle_end).
  - Theo dấu mảng parent ngược về v (cycle_start). Lưu lại các đỉnh trên đường đi này vào một danh sách (ví dụ: std::vector<int> path).
  - Danh sách path hiện đang chứa các đỉnh từ u ngược về v (ví dụ: [u, parent[u], ..., v]). Đảo ngược danh sách này để có thứ tự từ v đến u ([v, ..., parent[u], u]).
  - Đường đi của chu trình hoàn chỉnh là v theo đường đi đã đảo ngược đến u, và cuối cùng quay lại v. Thêm đỉnh v vào cuối danh sách đã đảo ngược.
- Độ dài chu trình là số đỉnh trong danh sách cuối cùng.
- In độ dài chu trình và các đỉnh theo thứ tự.
Trường hợp không có giải pháp:
- Nếu sau khi hoàn thành DFS từ tất cả các đỉnh chưa thăm mà không tìm thấy chu trình (cờ hiệu found_cycle vẫn là false), in ra "IMPOSSIBLE".

Lưu ý:

Các đỉnh được đánh số từ 1 đến n. Cần xử lý chỉ mục (index) phù hợp nếu sử dụng mảng/vector 0-based.
Bài toán yêu cầu "đi qua một hoặc nhiều thành phố khác", điều này có nghĩa là độ dài chu trình phải ít nhất là 3 (start -> intermediate -> start). Chu trình được phát hiện bởi DFS theo cách trên (v -> ... -> u -> v) sẽ có độ dài ít nhất là 3 nếu u không phải là v và v có ít nhất một con khác u trên đường đi từ v đến u trong cây DFS, hoặc độ dài là 3 nếu parent[u] == v. Cấu trúc phát hiện chu trình đảm bảo các đỉnh trung gian là duy nhất trong chu trình tìm được.
Bất kỳ chu trình hợp lệ nào cũng được chấp nhận, nên chu trình đầu tiên tìm thấy là đủ.

Tóm lại, các thành phần cần có trong code:

Danh sách kề adj.
Mảng state (ví dụ: 0=unvisited, 1=visiting, 2=visited).
Mảng parent.
Các biến để lưu cycle_start, cycle_end và cờ hiệu found_cycle.
Hàm dfs(u).
Hàm main để đọc input, khởi tạo, gọi DFS, và in output dựa trên found_cycle.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.