Khóa học CTDL và GT

Bài 21.4: Thuật toán tìm khớp dựa trên DFS

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau dấn thân vào một chủ đề thú vị trong lý thuyết đồ thị: tìm kiếm các cạnh đặc biệt mà việc loại bỏ chúng có thể gây ra hậu quả lớn đến cấu trúc liên thông của đồ thị. Trong ngữ cảnh của bài viết này, chúng ta sẽ tập trung vào việc tìm kiếm các cầu (bridge) trong đồ thị. Mặc dù tiêu đề sử dụng thuật ngữ "khớp" (đôi khi được dùng để chỉ đỉnh khớp - articulation point), thuật toán dựa trên DFS mà chúng ta thảo luận ở đây là phương pháp kinh điển để tìm ra các cầu trong đồ thị vô hướng. Cầu là những cạnh mà việc loại bỏ chúng sẽ làm tăng số lượng thành phần liên thông của đồ thị.

Hãy tưởng tượng bạn có một mạng lưới giao thông (các đỉnh là thành phố, các cạnh là con đường). Một "cầu" trong mạng lưới này chính là một con đường mà nếu nó bị sập, sẽ có ít nhất hai nhóm thành phố không thể di chuyển đến nhau được nữa. Việc xác định các "cầu" như vậy là cực kỳ quan trọng trong nhiều ứng dụng thực tế, từ thiết kế mạng lưới, phân tích mạng xã hội, cho đến tìm kiếm các điểm yếu trong hạ tầng.

Vậy, làm thế nào để chúng ta có thể tự động xác định những cạnh "yếu đuối" này trong một đồ thị lớn? Câu trả lời nằm ở việc tận dụng sức mạnh của thuật toán Tìm kiếm theo chiều sâu (Depth-First Search - DFS).

Tại sao DFS lại phù hợp để tìm Cầu?

DFS có một đặc điểm tuyệt vời là nó "đào sâu" vào một nhánh của đồ thị trước khi quay lui. Khi thực hiện DFS trên một đồ thị vô hướng, chúng ta có thể xây dựng một cây DFS (DFS tree). Các cạnh của đồ thị có thể được phân loại thành hai loại đối với cây DFS này:

1. Cạnh cây (Tree Edges): Các cạnh mà DFS đi qua để di chuyển từ một đỉnh chưa thăm đến một đỉnh mới.
2. Cạnh ngược (Back Edges): Các cạnh nối một đỉnh hiện tại đang thăm với một đỉnh tổ tiên của nó trong cây DFS (không phải là cha trực tiếp).

Các cầu trong đồ thị có một mối liên hệ đặc biệt với cấu trúc cây DFS và các cạnh ngược. Một cạnh (u, v) trong cây DFS (v là con của u) là một cây cầu nếu và chỉ nếu không có cạnh ngược nào từ cây con gốc v hoặc bất kỳ đỉnh nào trong cây con đó nối tới u hoặc bất kỳ tổ tiên nào của u.

Nói cách khác, nếu toàn bộ cây con dưới v chỉ có thể kết nối với phần còn lại của đồ thị bên trên u duy nhất qua cạnh (u, v), thì (u, v) chính là một cây cầu.

Thuật toán: Sử dụng tin và low

Để biến ý tưởng trên thành thuật toán cụ thể, chúng ta cần theo dõi hai thông tin quan trọng cho mỗi đỉnh u trong quá trình DFS:

1. Thời gian khám phá (tin[u]): Thời điểm (bước thời gian) mà đỉnh u được lần đầu tiên thăm bởi DFS. Chúng ta dùng một bộ đếm thời gian tăng dần trong quá trình duyệt.
2. Thời gian thăm lại thấp nhất (low[u]): Thời điểm khám phá (tin) thấp nhất mà đỉnh u hoặc bất kỳ đỉnh nào trong cây con gốc u có thể với tới thông qua các cạnh ngược (và có thể là các cạnh cây xuống các đỉnh khác rồi dùng cạnh ngược từ đó).

Chúng ta khởi tạo tin[u] và low[u] bằng giá trị tin[u] khi lần đầu thăm u. Sau đó, khi DFS thăm các đỉnh lân cận v của u:

• Nếu v là cha của u trong cây DFS: Bỏ qua cạnh này để tránh xử lý sai.
• Nếu v đã được thăm (và không phải cha): Đây là một cạnh ngược (u, v). Đỉnh u có thể kết nối với đỉnh v (đã thăm) qua cạnh này. Thời điểm thăm thấp nhất mà u có thể đạt tới qua cạnh này là tin[v]. Do đó, chúng ta cập nhật low[u] = min(low[u], tin[v]).
• Nếu v chưa được thăm: Đây là một cạnh cây (u, v). Chúng ta đệ quy gọi DFS cho v. Sau khi gọi đệ quy trả về, chúng ta đã có giá trị low[v] (thời điểm thăm lại thấp nhất mà cây con v có thể đạt tới). Đỉnh u có thể đạt tới bất kỳ đỉnh nào mà v có thể đạt tới. Do đó, chúng ta cập nhật low[u] = min(low[u], low[v]). Sau khi cập nhật low[u], chúng ta kiểm tra điều kiện để xác định cầu: Nếu low[v] > tin[u], thì cạnh (u, v) là một cây cầu.

Điều kiện low[v] > tin[u] nghĩa là gì? Nó có nghĩa là thời điểm thăm lại thấp nhất mà cây con gốc v có thể đạt tới (low[v]) vẫn lớn hơn thời điểm mà đỉnh u được khám phá (tin[u]). Điều này chỉ xảy ra khi không có bất kỳ cạnh ngược nào từ cây con gốc v kết nối được tới u hoặc bất kỳ tổ tiên nào của u. Do đó, cách duy nhất để đi từ cây con gốc v lên phần còn lại của đồ thị trên u là thông qua cạnh (u, v). Loại bỏ cạnh này sẽ chia tách đồ thị.

Chi Tiết Thuật Toán Bằng Pseudocode

Khởi tạo:
  vector<vector<int>> adj; // Danh sách kề
  vector<int> tin, low;   // Thời gian khám phá và thời gian thăm lại thấp nhất
  vector<bool> visited;   // Mảng đánh dấu đã thăm
  int timer;              // Bộ đếm thời gian
  vector<pair<int, int>> bridges; // Danh sách các cầu tìm được

Hàm DFS_Bridge(u, p): // u: đỉnh hiện tại, p: đỉnh cha trong cây DFS
  visited[u] = true;
  tin[u] = low[u] = timer++; // Gán thời gian khám phá và khởi tạo low

  // Duyệt qua các đỉnh lân cận v của u
  cho mỗi v trong adj[u]:
    nếu v == p: // Nếu v là cha, bỏ qua
      tiếp tục;

    nếu visited[v]: // Nếu v đã thăm (cạnh ngược)
      low[u] = min(low[u], tin[v]); // Cập nhật low[u] dựa trên thời gian khám phá của v
    else: // Nếu v chưa thăm (cạnh cây)
      DFS_Bridge(v, u); // Đệ quy thăm v
      low[u] = min(low[u], low[v]); // Cập nhật low[u] dựa trên low[v] (lan truyền giá trị thấp nhất từ cây con)

      // KIỂM TRA ĐIỀU KIỆN CẦU
      nếu low[v] > tin[u]:
        thêm cặp (u, v) vào danh sách bridges;

Hàm chính (Main):
  Đọc số đỉnh N, số cạnh M và danh sách cạnh.
  Khởi tạo adj với N đỉnh.
  Thêm các cạnh vào adj.
  Khởi tạo tin, low có kích thước N, giá trị -1.
  Khởi tạo visited có kích thước N, giá trị false.
  timer = 0;
  bridges.clear();

  // Duyệt qua tất cả các đỉnh để đảm bảo xử lý cả đồ thị không liên thông
  cho i từ 0 đến N-1:
    nếu không visited[i]:
      DFS_Bridge(i, -1); // Bắt đầu DFS từ đỉnh i, cha là -1 (không có cha)

  In ra danh sách bridges.

Minh Họa Bằng C++

Chúng ta sẽ cài đặt thuật toán này bằng C++.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

vector<vector<int>> adj; // Danh sách kề của đồ thị
vector<int> tin, low;   // Mảng lưu thời gian khám phá và thời gian thăm lại thấp nhất
vector<bool> visited;   // Mảng đánh dấu đỉnh đã thăm
int timer;              // Bộ đếm thời gian global
vector<pair<int, int>> bridges; // Danh sách lưu trữ các cầu tìm được

// Hàm DFS để tìm cầu
// u: đỉnh hiện tại
// p: đỉnh cha của u trong cây DFS (-1 nếu u là gốc của cây DFS)
void find_bridges_dfs(int u, int p = -1) {
    visited[u] = true;
    tin[u] = low[u] = timer++; // Gán thời gian khám phá và khởi tạo low[u]

    // Duyệt qua tất cả các đỉnh lân cận v của u
    for (int v : adj[u]) {
        if (v == p) {
            // Nếu v là cha của u trong cây DFS, bỏ qua
            continue;
        }

        if (visited[v]) {
            // Nếu v đã được thăm và không phải là cha của u,
            // thì (u, v) là một cạnh ngược.
            // low[u] có thể được cập nhật bằng tin[v]
            low[u] = min(low[u], tin[v]);
        } else {
            // Nếu v chưa được thăm, (u, v) là một cạnh cây.
            // Đệ quy gọi DFS cho v với u là cha
            find_bridges_dfs(v, u);

            // Sau khi đệ quy từ v trở về, cập nhật low[u].
            // low[u] có thể đạt tới bất kỳ đỉnh nào mà low[v] có thể đạt tới
            low[u] = min(low[u], low[v]);

            // Kiểm tra điều kiện để xác định cầu:
            // Nếu low[v] > tin[u], nghĩa là không có cạnh ngược nào
            // từ cây con gốc v nối tới u hoặc bất kỳ tổ tiên nào của u.
            // Vậy, (u, v) là một cầu.
            if (low[v] > tin[u]) {
                bridges.push_back({u, v});
            }
        }
    }
}

// Hàm chính để khởi tạo và gọi DFS
void find_all_bridges(int n) {
    adj.assign(n, vector<int>()); // Khởi tạo danh sách kề cho n đỉnh
    tin.assign(n, -1);           // Khởi tạo mảng tin với -1
    low.assign(n, -1);           // Khởi tạo mảng low với -1
    visited.assign(n, false);    // Khởi tạo mảng visited với false
    timer = 0;                   // Reset bộ đếm thời gian
    bridges.clear();             // Xóa danh sách cầu cũ

    // Do đồ thị có thể không liên thông, cần duyệt qua tất cả các đỉnh.
    // Nếu một đỉnh chưa được thăm, bắt đầu một đợt DFS mới từ đỉnh đó.
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            find_bridges_dfs(i); // Bắt đầu DFS từ đỉnh i, cha là -1
        }
    }
}

// Hàm thêm cạnh vào đồ thị (đồ thị vô hướng)
void add_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    cout << "--- Tim cau (Bridge) trong do thi ---" << endl;

    // Ví dụ 1: Đồ thị đơn giản
    // 0 -- 1 -- 2 -- 3 -- 4
    //      |    |
    //      -----
    // Cầu: (2, 3), (3, 4)
    cout << "\nVi du 1:" << endl;
    int n1 = 5;
    find_all_bridges(n1);
    add_edge(0, 1);
    add_edge(1, 2);
    add_edge(2, 0); // Tạo chu trình 0-1-2
    add_edge(2, 3); // Cau
    add_edge(3, 4); // Cau

    find_all_bridges(n1); // Chạy lại hàm tìm cầu sau khi thêm cạnh

    cout << "So dinh: " << n1 << endl;
    cout << "Cac cau tim duoc:";
    if (bridges.empty()) {
        cout << " Khong co cau nao." << endl;
    } else {
        cout << endl;
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ") ";
        }
        cout << endl;
    }

    // Ví dụ 2: Đồ thị phức tạp hơn
    // 0 -- 1 -- 3 -- 4 -- 6
    // |    |    |    |
    // 2 ----    5 ----
    // Cau: (1, 3), (4, 6)
    cout << "\nVi du 2:" << endl;
    int n2 = 7;
    find_all_bridges(n2); // Reset
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 2); // Tao chu trình 0-1-2
    add_edge(1, 3); // Cau
    add_edge(3, 4);
    add_edge(3, 5);
    add_edge(4, 5); // Tao chu trình 3-4-5
    add_edge(4, 6); // Cau

    find_all_bridges(n2); // Chạy lại hàm tìm cầu sau khi thêm cạnh

    cout << "So dinh: " << n2 << endl;
    cout << "Cac cau tim duoc:";
    if (bridges.empty()) {
        cout << " Khong co cau nao." << endl;
    } else {
        cout << endl;
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ") ";
        }
        cout << endl;
    }

     // Ví dụ 3: Đồ thị chỉ có chu trình
    // 0 -- 1 -- 2 -- 0
    // Không có cầu nào
    cout << "\nVi du 3:" << endl;
    int n3 = 3;
    find_all_bridges(n3); // Reset
    add_edge(0, 1);
    add_edge(1, 2);
    add_edge(2, 0); // Tạo chu trình 0-1-2

    find_all_bridges(n3); // Chạy lại hàm tìm cầu sau khi thêm cạnh

    cout << "So dinh: " << n3 << endl;
    cout << "Cac cau tim duoc:";
    if (bridges.empty()) {
        cout << " Khong co cau nao." << endl;
    } else {
        cout << endl;
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ") ";
        }
        cout << endl;
    }


    return 0;
}

Giải Thích Code C++

• Các Biến Toàn Cục:

  • adj: vector<vector<int>> biểu diễn danh sách kề của đồ thị. adj[i] là một vector chứa các đỉnh kề với đỉnh i.
  • tin: vector<int> lưu thời gian khám phá (tin[i]) cho mỗi đỉnh i. tin[i] là giá trị của timer khi đỉnh i được thăm lần đầu tiên.
  • low: vector<int> lưu thời gian thăm lại thấp nhất (low[i]) cho mỗi đỉnh i. low[i] là giá trị tin nhỏ nhất có thể đạt tới từ đỉnh i hoặc bất kỳ đỉnh nào trong cây con DFS của i thông qua các cạnh ngược.
  • visited: vector<bool> để đánh dấu đỉnh đã được thăm trong quá trình DFS.
  • timer: Một biến đếm thời gian đơn giản, tăng lên mỗi khi một đỉnh mới được khám phá lần đầu.
  • bridges: vector<pair<int, int>> để lưu trữ danh sách các cặp đỉnh tạo thành một cây cầu.

• Hàm find_bridges_dfs(int u, int p):

  • Đây là hàm DFS cốt lõi. u là đỉnh hiện tại đang thăm, p là đỉnh cha của u trong cây DFS (được dùng để phân biệt cạnh cây đi lên với cạnh ngược).
  • visited[u] = true;: Đánh dấu đỉnh u là đã thăm.
  • tin[u] = low[u] = timer++;: Gán thời gian khám phá cho u và khởi tạo low[u] ban đầu bằng chính tin[u]. Tăng timer.
  • Vòng lặp duyệt lân cận: Duyệt qua từng đỉnh v kề với u.
    • if (v == p) continue;: Nếu v là cha, bỏ qua để không đi ngược lên cây DFS ngay lập tức qua cạnh đã dùng để đến u.
    • if (visited[v]): Nếu v đã thăm. Điều này chỉ có thể xảy ra nếu (u, v) là một cạnh ngược (vì nếu v là con đã thăm thì v đã phải được xử lý trong đệ quy từ u). Chúng ta cập nhật low[u] = min(low[u], tin[v]). Điều này phản ánh rằng từ u, chúng ta có thể đi qua cạnh ngược (u, v) để đến một đỉnh đã thăm v tại thời điểm tin[v].
    • else: Nếu v chưa thăm. Đây là cạnh cây (u, v).
      • find_bridges_dfs(v, u);: Đệ quy gọi DFS cho v với u làm cha.
      • low[u] = min(low[u], low[v]);: Sau khi gọi đệ quy cho v trả về, low[v] chứa thời điểm thăm lại thấp nhất mà cây con gốc v có thể đạt tới. Đỉnh u có thể "kế thừa" khả năng này của cây con v, nên chúng ta cập nhật low[u] bằng min(low[u], low[v]).
      • if (low[v] > tin[u]): Đây là điều kiện kiểm tra cầu. Nếu giá trị low của cây con v (thời điểm thăm lại sớm nhất từ cây con v) lớn hơn thời điểm mà u được khám phá (tin[u]), thì không có cách nào từ cây con v đi ngược lên u hoặc các tổ tiên của u ngoại trừ qua cạnh (u, v). Do đó, (u, v) là một cầu và được thêm vào danh sách bridges.

• Hàm find_all_bridges(int n):

  • Hàm này chuẩn bị các cấu trúc dữ liệu (adj, tin, low, visited, bridges) cho một đồ thị có n đỉnh và khởi tạo timer.
  • adj.assign(n, vector<int>());: Tạo danh sách kề cho n đỉnh rỗng.
  • Các assign khác cũng khởi tạo các vector với kích thước n và giá trị mặc định.
  • timer = 0; bridges.clear();: Đảm bảo bộ đếm thời gian và danh sách cầu được reset cho mỗi lần tìm kiếm trên một đồ thị mới.
  • Vòng lặp chính: for (int i = 0; i < n; ++i). Vòng lặp này cần thiết để đảm bảo thuật toán hoạt động đúng cho cả đồ thị không liên thông. Nếu một đỉnh i chưa được thăm, nó là một phần của một thành phần liên thông mới mà DFS chưa tiếp cận. Chúng ta bắt đầu một đợt DFS mới từ đỉnh i (với cha là -1 vì nó là gốc của cây DFS trong thành phần này).

• Hàm add_edge(int u, int v): Hàm tiện ích để thêm cạnh vào danh sách kề cho đồ thị vô hướng.

• Hàm main():

  • Chứa các ví dụ minh họa. Đối với mỗi ví dụ, nó gọi find_all_bridges() để reset trạng thái, thêm các cạnh tương ứng với đồ thị ví dụ, sau đó gọi lại find_all_bridges() (hoặc bạn có thể tích hợp việc thêm cạnh vào một hàm setup riêng trước khi gọi DFS) và in kết quả.

Ví Dụ Minh Họa Chi Tiết Hơn

Hãy xem xét Ví dụ 1: Đồ thị: 0-1, 1-2, 2-0, 2-3, 3-4 Đỉnh: 0, 1, 2, 3, 4

Giả sử DFS bắt đầu từ đỉnh 0:

1. DFS(0, -1):

   • visited[0] = true, tin[0] = low[0] = timer = 0, timer = 1.
   • Neighbors của 0: 1, 2.
   • Thăm 1: Chưa thăm. Gọi DFS(1, 0).

2. DFS(1, 0):

   • visited[1] = true, tin[1] = low[1] = timer = 1, timer = 2.
   • Neighbors của 1: 0, 2.
   • Thăm 0: Là cha (p == 0). Bỏ qua.
   • Thăm 2: Chưa thăm. Gọi DFS(2, 1).

3. DFS(2, 1):

   • visited[2] = true, tin[2] = low[2] = timer = 2, timer = 3.
   • Neighbors của 2: 1, 0, 3.
   • Thăm 1: Là cha (p == 1). Bỏ qua.
   • Thăm 0: Đã thăm (visited[0] == true) và không phải cha. Đây là cạnh ngược (2, 0). low[2] = min(low[2], tin[0]) = min(2, 0) = 0.
   • Thăm 3: Chưa thăm. Gọi DFS(3, 2).

4. DFS(3, 2):

   • visited[3] = true, tin[3] = low[3] = timer = 3, timer = 4.
   • Neighbors của 3: 2, 4.
   • Thăm 2: Là cha (p == 2). Bỏ qua.
   • Thăm 4: Chưa thăm. Gọi DFS(4, 3).

5. DFS(4, 3):

   • visited[4] = true, tin[4] = low[4] = timer = 4, timer = 5.
   • Neighbors của 4: 3.
   • Thăm 3: Là cha (p == 3). Bỏ qua.
   • Không còn lân cận nào. Trả về từ DFS(4, 3).

6. Quay lại DFS(3, 2):

   • Đã thăm 4 (con). Cập nhật low[3] = min(low[3], low[4]) = min(3, 4) = 3.
   • Kiểm tra cầu (3, 4): low[4] (4) > tin[3] (3). Đúng! Cạnh (3, 4) là cầu. Thêm (3, 4) vào bridges.
   • Không còn lân cận nào của 3. Trả về từ DFS(3, 2).

7. Quay lại DFS(2, 1):

   • Đã thăm 3 (con). Cập nhật low[2] = min(low[2], low[3]) = min(0, 3) = 0. (Giá trị low[2] vẫn là 0 do cạnh ngược (2,0)).
   • Kiểm tra cầu (2, 3): low[3] (3) > tin[2] (2). Đúng! Cạnh (2, 3) là cầu. Thêm (2, 3) vào bridges.
   • Không còn lân cận nào của 2. Trả về từ DFS(2, 1).

8. Quay lại DFS(1, 0):

   • Đã thăm 2 (con). Cập nhật low[1] = min(low[1], low[2]) = min(1, 0) = 0. (Giá trị low[1] là 0 do low[2] là 0).
   • Kiểm tra cầu (1, 2): low[2] (0) > tin[1] (1). Sai! 0 không lớn hơn 1. (1, 2) không phải cầu (vì có cạnh ngược (2, 0)).
   • Không còn lân cận nào của 1. Trả về từ DFS(1, 0).

9. Quay lại DFS(0, -1):

   • Đã thăm 1 (con). Cập nhật low[0] = min(low[0], low[1]) = min(0, 0) = 0.
   • Kiểm tra cầu (0, 1): low[1] (0) > tin[0] (0). Sai! 0 không lớn hơn 0. (0, 1) không phải cầu.
   • Đã thăm 2 (lân cận đã thăm, không phải cha). low[0] đã được cập nhật thành min(low[0], tin[2]) = min(0, 2) = 0 trước khi thăm 1.
   • Không còn lân cận nào của 0. Trả về từ DFS(0, -1).

Quá trình DFS hoàn thành. Các đỉnh 0, 1, 2, 3, 4 đều đã được thăm. Danh sách bridges chứa (3, 4) và (2, 3).

Độ Phức Tạp

• Thời gian: Thuật toán này về cơ bản là một biến thể của DFS, mỗi đỉnh và mỗi cạnh được thăm đúng một lần. Do đó, độ phức tạp thời gian là O(V + E), trong đó V là số đỉnh và E là số cạnh của đồ thị.
• Không gian: Chúng ta cần lưu trữ danh sách kề (O(V + E)), các mảng tin, low, visited (O(V)) và stack đệ quy cho DFS (trong trường hợp xấu nhất là O(V)). Do đó, độ phức tạp không gian là O(V + E).

Bài tập ví dụ:

Kiểm tra đường bay

Trong một dự án về hàng không, FullHouse Dev được giao nhiệm vụ kiểm tra tính khả thi của hệ thống đường bay. Họ cần phải xác định xem liệu có thể di chuyển giữa bất kỳ hai thành phố nào trong hệ thống hay không.

Bài toán

Có \(n\) thành phố và \(m\) đường bay một chiều. Nhiệm vụ của FullHouse Dev là kiểm tra xem liệu có thể di chuyển từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác bằng cách sử dụng các đường bay hiện có hay không.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và số lượng đường bay. Các thành phố được đánh số từ \(1\) đến \(n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thể hiện một đường bay một chiều từ thành phố \(a\) đến thành phố \(b\).

OUTPUT FORMAT:

• In ra "YES" nếu có thể di chuyển giữa mọi cặp thành phố.
• In ra "NO" nếu không thể, và in thêm hai số \(a\) và \(b\) thể hiện không thể di chuyển từ thành phố \(a\) đến thành phố \(b\).
• Nếu có nhiều đáp án, có thể in ra bất kỳ đáp án nào.

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

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

OUTPUT

NO
4 2

Giải thích

Trong ví dụ này, không thể di chuyển từ thành phố 4 đến thành phố 2 bằng bất kỳ tổ hợp đường bay nào. Do đó, đáp án là "NO" và một cặp thành phố không thể kết nối là 4 và 2. Ok, đây là hướng dẫn giải bài "Kiểm tra đường bay" một cách ngắn gọn bằng C++ sử dụng thuật toán đồ thị:

1. Biểu diễn đồ thị:

   • Sử dụng danh sách kề (adjacency list) để lưu trữ đồ thị gốc (các đường bay một chiều). Vector of vectors vector<vector<int>> adj; là phù hợp. Kích thước là n+1.
   • Bạn cũng cần danh sách kề cho đồ thị chuyển vị (transpose graph), nơi tất cả các cạnh bị đảo ngược chiều. vector<vector<int>> rev_adj; cũng có kích thước n+1.
   • Khi đọc đầu vào a b, thêm cạnh a -> b vào adj và cạnh b -> a vào rev_adj.

2. Kiểm tra tính liên thông mạnh:

   • Một đồ thị có hướng liên thông mạnh (strongly connected) khi và chỉ khi bạn có thể đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác.
   • Cách kiểm tra hiệu quả là thực hiện hai lần duyệt đồ thị (ví dụ: DFS hoặc BFS) từ một đỉnh bất kỳ (chọn đỉnh 1 cho tiện):
     • Lần 1: Duyệt DFS/BFS từ đỉnh 1 trên đồ thị gốc. Đếm số đỉnh có thể thăm được.
     • Lần 2: Nếu lần 1 thăm được tất cả N đỉnh, tiếp tục duyệt DFS/BFS từ đỉnh 1 trên đồ thị chuyển vị. Đếm số đỉnh có thể thăm được.

3. Phân tích kết quả:

   • Nếu lần duyệt đầu tiên (trên đồ thị gốc từ đỉnh 1) không thăm được tất cả N đỉnh: Điều này có nghĩa là có đỉnh v mà đỉnh 1 không thể đến được. Đồ thị không liên thông mạnh. In ra "NO" và cặp "1 v" (tìm một đỉnh v đầu tiên không được thăm).
   • Nếu lần duyệt đầu tiên thăm được tất cả N đỉnh, nhưng lần duyệt thứ hai (trên đồ thị chuyển vị từ đỉnh 1) không thăm được tất cả N đỉnh: Điều này có nghĩa là có đỉnh v mà đỉnh 1 không thể đến được trong đồ thị chuyển vị. Tương đương, trong đồ thị gốc, đỉnh v không thể đến được đỉnh 1. Đồ thị không liên thông mạnh. In ra "NO" và cặp "v 1" (tìm một đỉnh v đầu tiên không được thăm trong lần duyệt thứ hai).
   • Nếu cả hai lần duyệt đều thăm được tất cả N đỉnh: Điều này đảm bảo rằng từ đỉnh 1 có thể đến mọi đỉnh khác, và mọi đỉnh khác có thể đến được đỉnh 1. Kết hợp với tính chất bắc cầu của đường đi, điều này chứng tỏ mọi cặp đỉnh đều có thể di chuyển qua lại. Đồ thị liên thông mạnh. In ra "YES".

4. Triển khai DFS/BFS:

   • Viết một hàm DFS hoặc BFS thông thường nhận vào đỉnh bắt đầu, danh sách kề của đồ thị cần duyệt, và một mảng/vector visited để đánh dấu các đỉnh đã thăm.
   • Trong hàm này, đếm hoặc trả về số lượng đỉnh đã thăm được.

5. Lưu ý khi tìm cặp (a, b):

   • Nếu lần duyệt đầu tiên thất bại, bạn cần tìm một đỉnh v chưa được thăm. Cách đơn giản nhất là duyệt từ 1 đến N và tìm đỉnh i đầu tiên có visited[i] là false. Cặp là (1, i).
   • Nếu lần duyệt thứ hai thất bại, bạn cần tìm một đỉnh v chưa được thăm trong đồ thị chuyển vị. Cách đơn giản nhất là duyệt từ 1 đến N và tìm đỉnh i đầu tiên có visited_rev[i] là false. Cặp là (i, 1).

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