Bài 23.4. Phát hiện chu trình bằng Tarjan

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của chúng ta! Hôm nay, chúng ta sẽ lặn sâu vào một chủ đề thú vị và cực kỳ quan trọng trong lý thuyết đồ thị: Phát hiện chu trình (Cycles) trong đồ thị có hướng. Đặc biệt, chúng ta sẽ khám phá sức mạnh của một trong những thuật toán kinh điển cho bài toán này và các bài toán liên quan: Thuật toán Tarjan.

Chu trình trong đồ thị có hướng xuất hiện trong rất nhiều bài toán thực tế: phát hiện bế tắc (deadlock) trong hệ điều hành, phân tích luồng điều khiển chương trình, kiểm tra sự phụ thuộc giữa các tác vụ (task dependencies), v.v. Việc nhận diện và hiểu rõ các chu trình là bước đầu tiên để giải quyết các vấn đề này.

Đối với đồ thị vô hướng, việc phát hiện chu trình khá đơn giản bằng DFS. Tuy nhiên, trong đồ thị có hướng, khái niệm chu trình phức tạp hơn. Chúng ta có khái niệm về chu trình đơn giản (simple cycle) và thành phần liên thông mạnh (Strongly Connected Component - SCC). Một SCC là một tập hợp các đỉnh mà với bất kỳ hai đỉnh u và v nào trong tập hợp đó, đều tồn tại đường đi từ u đến v và từ v đến u. Các SCC có kích thước lớn hơn 1 (hoặc kích thước 1 với cạnh khuyên/self-loop) chắc chắn chứa chu trình mạnh. Ngược lại, mọi chu trình mạnh đều nằm gọn trong một SCC.

Thuật toán Tarjan không chỉ phát hiện chu trình, mà còn phân rã đồ thị thành các SCC. Từ các SCC này, chúng ta dễ dàng suy ra sự tồn tại và cấu trúc của các chu trình mạnh.

Tại sao lại là Tarjan?

Có những thuật toán khác để tìm SCCs hoặc phát hiện chu trình, như thuật toán Kosaraju hay thuật toán dựa trên DFS hai lần. Tuy nhiên, thuật toán Tarjan có một ưu điểm nổi bật là nó chỉ cần một lần duyệt DFS duy nhất (single pass DFS), làm cho nó hiệu quả về mặt thời gian (O(V+E)) và thường được ưa chuộng trong thực tế.

Ý tưởng cốt lõi của Tarjan dựa trên việc theo dõi thứ tự duyệt DFS của các đỉnh và khả năng "liên kết ngược" (back-linking) của chúng đến các đỉnh tổ tiên vẫn còn nằm trong cây DFS hiện tại.

Các Khái Niệm Cốt Lõi Của Tarjan

Để hiểu thuật toán Tarjan, chúng ta cần làm quen với vài khái niệm chính được sử dụng trong quá trình duyệt DFS của nó:

Thời gian khám phá (dfn - Discovery Time): Mỗi đỉnh u được gán một giá trị dfn[u], là thứ tự mà đỉnh đó được thăm lần đầu tiên trong quá trình duyệt DFS. Chúng ta dùng một bộ đếm thời gian (timer hoặc index) tăng dần mỗi khi thăm một đỉnh mới.
Giá trị liên kết thấp (low - Low-Link Value): Đối với mỗi đỉnh u, low[u] là giá trị dfn nhỏ nhất của bất kỳ đỉnh nào có thể reachable từ u (bao gồm cả u đó) thông qua các cạnh trong cây DFS và tối đa một cạnh ngược (back edge) đến một đỉnh vẫn còn đang nằm trong stack xử lý DFS hiện tại. Điểm mấu chốt là chỉ xét các cạnh ngược về các đỉnh vẫn đang được xem xét (chưa được gán vào SCC nào).
Stack xử lý: Một stack tạm thời chứa các đỉnh đang trong quá trình duyệt DFS và chưa được gán vào bất kỳ SCC nào.
Trạng thái onStack: Một mảng boolean để kiểm tra nhanh xem một đỉnh có đang nằm trong stack xử lý hay không.

Thuật Toán Tarjan: Từng Bước Một

Thuật toán hoạt động như sau:

Chúng ta duyệt qua tất cả các đỉnh của đồ thị. Nếu một đỉnh chưa được thăm (dfn == -1), ta bắt đầu một cuộc duyệt DFS từ đỉnh đó.
Trong hàm DFS cho đỉnh u:
- Bước 1: Khởi tạo. Gán dfn[u] = low[u] = timer++. Đẩy u vào stack xử lý và đánh dấu onStack[u] = true.
- Bước 2: Thăm các đỉnh kề. Duyệt qua tất cả các đỉnh v kề với u (nghĩa là có cạnh u -> v):
  - Trường hợp 1: v chưa được thăm (dfn[v] == -1): Đây là một cạnh cây (tree edge). Ta gọi đệ quy dfs(v). Sau khi lời gọi đệ quy trả về, ta cập nhật low[u] = min(low[u], low[v]). Điều này có nghĩa là u có thể liên kết thấp đến bất kỳ đâu mà v có thể liên kết thấp đến.
  - Trường hợp 2: v đã được thăm (dfn[v] != -1) và v đang nằm trong stack xử lý (onStack[v] == true): Đây là một cạnh ngược (back edge) hoặc một cạnh chéo (cross edge) đến một đỉnh vẫn đang trong cây DFS hiện tại. Đỉnh u có thể "nhìn thấy" v thông qua cạnh này. Ta cập nhật low[u] = min(low[u], dfn[v]). Lưu ý chúng ta dùng dfn[v] chứ không phải low[v] vì chúng ta chỉ quan tâm đến việc u có thể "quay ngược" về một tổ tiên (v có dfn[v] nhỏ hơn dfn[u]) đang còn trong stack.
  - Trường hợp 3: v đã được thăm (dfn[v] != -1) nhưng v không nằm trong stack xử lý (onStack[v] == false): Đây là một cạnh chéo hoặc cạnh xuôi (forward edge) đến một đỉnh đã được gán vào một SCC trước đó. Cạnh này không liên quan đến việc tính low[u] vì v và các đỉnh reachable từ nó đã thuộc về một SCC hoàn chỉnh. Ta bỏ qua cạnh này khi cập nhật low[u].
- Bước 3: Phát hiện và xử lý SCC. Sau khi đã duyệt hết tất cả các đỉnh kề của u, nếu ta thấy low[u] == dfn[u], điều này có nghĩa là đỉnh u là gốc của một SCC. Tại sao? Bởi vì low[u] bằng dfn[u] có nghĩa là không có đỉnh nào reachable từ u (bao gồm cả các đỉnh trong cây con gốc u và qua một cạnh ngược) có dfn nhỏ hơn dfn[u] và vẫn còn đang nằm trong stack. Điều này chỉ xảy ra khi tất cả các đỉnh từ u trở xuống trong cây DFS hiện tại và các đỉnh liên kết ngược về u (hoặc các tổ tiên của u nhưng không cao hơn điểm cắt tiềm năng tại u) tạo thành một SCC độc lập.
  - Khi phát hiện SCC tại gốc u, ta sẽ pop các đỉnh từ stack xử lý cho đến khi pop được đỉnh u. Tất cả các đỉnh được pop ra trong quá trình này (bao gồm cả u) chính là các đỉnh của một SCC. Ta đánh dấu onStack của chúng thành false. Nếu SCC này có kích thước lớn hơn 1, hoặc là đỉnh u có cạnh khuyên về chính nó (cần kiểm tra thêm cạnh kề), thì SCC này chứa một chu trình mạnh.

Quá trình này lặp lại cho đến khi tất cả các đỉnh đã được thăm và gán vào một SCC.

Cài Đặt Thuật Toán Tarjan bằng C++

Chúng ta sẽ cần:

Một danh sách kề (adj) để biểu diễn đồ thị.
Các mảng dfn, low để lưu thời gian khám phá và giá trị liên kết thấp.
Một stack (stk) và mảng boolean onStack.
Một biến đếm thời gian timer.
Biến đếm SCC scc_count (tùy chọn, để đánh số các SCC).
Một mảng/vector để lưu trữ các SCC (tùy chọn).

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 10005; // Kích thước tối đa của đồ thị
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN];
bool onStack[MAXN];
stack<int> stk;
int timer; // Biến đếm thời gian khám phá
int scc_count; // Biến đếm số lượng SCC tìm được
vector<vector<int>> sccs; // Lưu trữ các SCC tìm được

// Hàm DFS chính của thuật toán Tarjan
void tarjan_dfs(int u) {
    // Bước 1: Khởi tạo dfn, low, push vào stack
    dfn[u] = low[u] = timer++;
    stk.push(u);
    onStack[u] = true;

    // Bước 2: Thăm các đỉnh kề của u
    for (int v : adj[u]) {
        if (dfn[v] == -1) {
            // Trường hợp 1: v chưa được thăm -> cạnh cây
            tarjan_dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (onStack[v]) {
            // Trường hợp 2: v đã thăm và đang ở trong stack -> cạnh ngược hoặc cạnh chéo đến đỉnh trong cây DFS hiện tại
            // Cập nhật low[u] dựa trên dfn[v]
            low[u] = min(low[u], dfn[v]);
        }
        // Trường hợp 3: v đã thăm và không ở trong stack -> cạnh chéo/xuôi đến SCC đã xử lý, bỏ qua
    }

    // Bước 3: Phát hiện và xử lý SCC tại gốc u
    if (low[u] == dfn[u]) {
        // u là gốc của một SCC
        vector<int> current_scc;
        int node;
        do {
            node = stk.top();
            stk.pop();
            onStack[node] = false;
            current_scc.push_back(node);
        } while (node != u);

        sccs.push_back(current_scc); // Lưu SCC vừa tìm được
        scc_count++;

        // Một SCC có kích thước > 1, hoặc kích thước 1 nhưng có cạnh khuyên, chứa chu trình
        // Việc kiểm tra cạnh khuyên cho SCC kích thước 1 có thể cần logic bổ sung
        // nhưng thông thường SCC kích thước > 1 đã đủ để khẳng định có chu trình mạnh.
        if (current_scc.size() > 1) {
            cout << "Phát hiện chu trình mạnh trong SCC: ";
            for (int i = 0; i < current_scc.size(); ++i) {
                cout << current_scc[i] << (i == current_scc.size() - 1 ? "" : ", ");
            }
            cout << endl;
        } else {
            // Kích thước 1. Cần kiểm tra xem có cạnh khuyên không.
            // Cách đơn giản là duyệt lại các đỉnh kề của node đó.
            int single_node = current_scc[0];
            bool has_self_loop = false;
            for(int neighbor : adj[single_node]) {
                if (neighbor == single_node) {
                    has_self_loop = true;
                    break;
                }
            }
            if (has_self_loop) {
                 cout << "Phát hiện chu trình (cạnh khuyên) tại đỉnh: " << single_node << endl;
            }
        }
    }
}

// Hàm chính để chạy thuật toán Tarjan trên toàn bộ đồ thị
void find_sccs(int n) {
    // Khởi tạo các mảng và biến
    for (int i = 0; i < n; ++i) {
        dfn[i] = -1; // Đánh dấu chưa thăm
        low[i] = -1;
        onStack[i] = false;
    }
    while (!stk.empty()) stk.pop(); // Xóa stack nếu còn dư từ lần chạy trước (không cần nếu dùng toàn cục và chạy 1 lần)
    timer = 0;
    scc_count = 0;
    sccs.clear(); // Xóa các SCC cũ

    // Duyệt qua tất cả các đỉnh, bắt đầu DFS nếu đỉnh chưa được thăm
    for (int i = 0; i < n; ++i) {
        if (dfn[i] == -1) {
            tarjan_dfs(i);
        }
    }
}

// Hàm thêm cạnh (với đỉnh 0-based)
void add_edge(int u, int v) {
    adj[u].push_back(v);
}

// Hàm reset đồ thị (để chạy nhiều ví dụ)
void reset_graph(int n) {
    for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }
}

Giải thích Code C++:

Biến toàn cục/mảng: adj là danh sách kề lưu đồ thị. dfn, low, onStack là các mảng lưu trạng thái và giá trị của các đỉnh. stk là stack xử lý. timer đếm thời gian DFS. scc_count đếm số SCC. sccs lưu trữ danh sách các SCC (mỗi SCC là một vector các đỉnh).
tarjan_dfs(int u): Đây là hàm DFS đệ quy chính.
- Khi vào hàm, đỉnh u được gán dfn[u] và low[u] bằng giá trị timer hiện tại, sau đó timer tăng. u được đẩy vào stk và đánh dấu onStack[u] = true.
- Vòng lặp for (int v : adj[u]) duyệt qua các đỉnh kề.
  - Nếu v chưa thăm (dfn[v] == -1), ta đệ quy vào v. Sau khi dfs(v) hoàn thành, low[u] được cập nhật bằng min(low[u], low[v]) vì u có thể thông qua v để đến được các đỉnh mà v đến được với low nhỏ nhất.
  - Nếu v đã thăm và onStack[v] là true, nghĩa là v là một tổ tiên của u (hoặc một đỉnh khác trong cùng nhánh DFS chưa hoàn thành). Ta có cạnh u -> v. Cạnh này cho phép u truy cập v. low[u] được cập nhật bằng min(low[u], dfn[v]). Ta dùng dfn[v] vì đây là thời điểm sớm nhất ta có thể quay ngược về một đỉnh trong stack thông qua v.
  - Nếu v đã thăm nhưng không onStack[v], v đã được xử lý và gán vào một SCC khác. Cạnh u -> v là cạnh giữa các SCC, không ảnh hưởng đến low[u] trong ngữ cảnh tìm SCC hiện tại.
- Sau vòng lặp, kiểm tra if (low[u] == dfn[u]). Nếu điều kiện này đúng, u là gốc của một SCC. Vòng do-while pop các đỉnh từ stack cho đến khi gặp u, gom chúng vào một vector representing the SCC, và đánh dấu onStack của chúng là false.
- Logic kiểm tra chu trình: Nếu kích thước của SCC lớn hơn 1, hoặc kích thước 1 nhưng có cạnh khuyên, ta in ra thông báo phát hiện chu trình mạnh.
find_sccs(int n): Hàm này khởi tạo các mảng và biến, sau đó duyệt qua tất cả các đỉnh từ 0 đến n-1. Nếu một đỉnh chưa được thăm (dfn[i] == -1), nó sẽ gọi tarjan_dfs để bắt đầu một cuộc duyệt mới từ đỉnh đó. Điều này đảm bảo mọi thành phần liên thông của đồ thị (không chỉ thành phần chứa đỉnh 0) đều được xử lý.
add_edge và reset_graph: Các hàm tiện ích để xây dựng và xóa đồ thị giữa các ví dụ.

Ví Dụ Minh Họa

Chúng ta sẽ áp dụng thuật toán này vào một vài đồ thị cụ thể để thấy cách nó hoạt động và phát hiện chu trình.

Ví Dụ 1: Chu trình đơn giản

Xét đồ thị với 4 đỉnh (0, 1, 2, 3) và các cạnh: 0 -> 1, 1 -> 2, 2 -> 0, 1 -> 3.

Đồ thị này chứa một chu trình mạnh: 0 -> 1 -> 2 -> 0. Đỉnh 3 là một đỉnh "treo" ra từ chu trình.

// Sử dụng các hàm đã định nghĩa ở trên

int main() {
    cout << "--- Ví dụ 1: Chu trình đơn giản ---" << endl;
    int n1 = 4;
    reset_graph(n1);

    add_edge(0, 1);
    add_edge(1, 2);
    add_edge(2, 0);
    add_edge(1, 3);

    find_sccs(n1);

    cout << "Tổng số SCC tìm được: " << scc_count << endl;
    cout << "Các SCC: " << endl;
    for(const auto& scc : sccs) {
        cout << "[";
        for(size_t i = 0; i < scc.size(); ++i) {
            cout << scc[i] << (i == scc.size() - 1 ? "" : ", ");
        }
        cout << "]" << endl;
    }
    cout << endl;

    return 0;
}

Phân tích Ví dụ 1:

find_sccs(4) được gọi. dfn và low đều là -1. timer = 0.
Bắt đầu DFS từ 0 (dfn[0] == -1):
- tarjan_dfs(0): dfn[0]=low[0]=0, timer=1. Stack: [0], onStack[0]=true.
- Duyệt cạnh 0 -> 1: dfn[1] == -1. Gọi tarjan_dfs(1).
  - tarjan_dfs(1): dfn[1]=low[1]=1, timer=2. Stack: [0, 1], onStack[1]=true.
  - Duyệt cạnh 1 -> 2: dfn[2] == -1. Gọi tarjan_dfs(2).
    - tarjan_dfs(2): dfn[2]=low[2]=2, timer=3. Stack: [0, 1, 2], onStack[2]=true.
    - Duyệt cạnh 2 -> 0: dfn[0] == 0 và onStack[0] là true. Cập nhật low[2] = min(low[2], dfn[0]) = min(2, 0) = 0. low[2] bây giờ là 0.
    - Không còn cạnh kề từ 2. low[2] (0) != dfn[2] (2). Chưa phát hiện SCC. Trở về 1.
  - Sau khi tarjan_dfs(2) trả về, low[1] = min(low[1], low[2]) = min(1, 0) = 0. low[1] bây giờ là 0.
  - Duyệt cạnh 1 -> 3: dfn[3] == -1. Gọi tarjan_dfs(3).
    - tarjan_dfs(3): dfn[3]=low[3]=3, timer=4. Stack: [0, 1, 2, 3], onStack[3]=true.
    - Đỉnh 3 không có đỉnh kề. low[3] (3) == dfn[3] (3). Phát hiện SCC tại gốc 3.
    - Pop 3: Stack [0, 1, 2]. onStack[3]=false. SCC: [3]. Kích thước 1, không có cạnh khuyên. Không in chu trình. scc_count=1, sccs = [[3]].
    - Trở về 1.
  - Sau khi tarjan_dfs(3) trả về, low[1] (0) vẫn là 0.
  - Không còn cạnh kề từ 1. low[1] (0) != dfn[1] (1). Chưa phát hiện SCC. Trở về 0.
- Sau khi tarjan_dfs(1) trả về, low[0] = min(low[0], low[1]) = min(0, 0) = 0. low[0] vẫn là 0.
- Không còn cạnh kề từ 0. low[0] (0) == dfn[0] (0). Phát hiện SCC tại gốc 0.
- Pop từ stack ([0, 1, 2]): Pop 2 (onStack[2]=false), SCC: [2]. Pop 1 (onStack[1]=false), SCC: [2, 1]. Pop 0 (onStack[0]=false), SCC: [2, 1, 0]. Dừng vì gặp 0.
- Lưu SCC: [2, 1, 0]. Kích thước 3 (> 1). In thông báo chu trình mạnh. scc_count=2, sccs = [[3], [2, 1, 0]].
- tarjan_dfs(0) kết thúc.
Vòng lặp chính tiếp tục. Đỉnh 1, 2, 3 đã được thăm (dfn != -1).
Kết thúc find_sccs.

Kết quả output sẽ in ra một SCC là [2, 1, 0] và thông báo có chu trình trong đó, cùng với SCC [3].

Ví Dụ 2: Nhiều SCC và Cạnh giữa các SCC

Xét đồ thị với 6 đỉnh (0-5) và các cạnh: 0 -> 1, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 3.

Đồ thị này có hai SCC mạnh: {0, 1, 2} và {3, 4, 5}. Có cạnh 2 -> 3 nối hai SCC này.

// Sử dụng các hàm đã định nghĩa ở trên

int main() {
    cout << "--- Ví dụ 2: Nhiều SCC và Cạnh giữa các SCC ---" << endl;
    int n2 = 6;
    reset_graph(n2);

    add_edge(0, 1);
    add_edge(1, 2);
    add_edge(2, 0); // SCC 1: {0, 1, 2}
    add_edge(2, 3); // Cạnh nối 2 SCC
    add_edge(3, 4);
    add_edge(4, 5);
    add_edge(5, 3); // SCC 2: {3, 4, 5}

    find_sccs(n2);

    cout << "Tổng số SCC tìm được: " << scc_count << endl;
    cout << "Các SCC: " << endl;
     for(const auto& scc : sccs) {
        cout << "[";
        for(size_t i = 0; i < scc.size(); ++i) {
            cout << scc[i] << (i == scc.size() - 1 ? "" : ", ");
        }
        cout << "]" << endl;
    }
    cout << endl;

    return 0;
}

Phân tích Ví dụ 2:

find_sccs(6) được gọi. dfn/low -1, timer=0, stack rỗng, onStack false.
Bắt đầu DFS từ 0 (dfn[0] == -1):
- tarjan_dfs(0): dfn[0]=low[0]=0, timer=1. Stack: [0], onStack[0]=true.
- 0 -> 1: dfn[1] == -1. Gọi tarjan_dfs(1).
  - tarjan_dfs(1): dfn[1]=low[1]=1, timer=2. Stack: [0, 1], onStack[1]=true.
  - 1 -> 2: dfn[2] == -1. Gọi tarjan_dfs(2).
    - tarjan_dfs(2): dfn[2]=low[2]=2, timer=3. Stack: [0, 1, 2], onStack[2]=true.
    - 2 -> 0: dfn[0]=0, onStack[0]=true. low[2] = min(low[2], dfn[0]) = min(2, 0) = 0.
    - 2 -> 3: dfn[3] == -1. Gọi tarjan_dfs(3).
      - tarjan_dfs(3): dfn[3]=low[3]=3, timer=4. Stack: [0, 1, 2, 3], onStack[3]=true.
      - 3 -> 4: dfn[4] == -1. Gọi tarjan_dfs(4).
        
        tarjan_dfs(4): dfn[4]=low[4]=4, timer=5. Stack: [0, 1, 2, 3, 4], onStack[4]=true.
        
        4 -> 5: dfn[5] == -1. Gọi tarjan_dfs(5).
        
        tarjan_dfs(5): dfn[5]=low[5]=5, timer=6. Stack: [0, 1, 2, 3, 4, 5], onStack[5]=true. 5 -> 3: dfn[3]=3, onStack[3]=true. low[5] = min(low[5], dfn[3]) = min(5, 3) = 3. * Đỉnh 5 không còn kề. low[5] (3) != dfn[5] (5). Trở về 4.
        
        Sau tarjan_dfs(5), low[4] = min(low[4], low[5]) = min(4, 3) = 3.
        
        Đỉnh 4 không còn kề. low[4] (3) != dfn[4] (4). Trở về 3.
      - Sau tarjan_dfs(4), low[3] = min(low[3], low[4]) = min(3, 3) = 3.
      - Đỉnh 3 không còn kề (trừ 4 đã thăm). low[3] (3) == dfn[3] (3). Phát hiện SCC tại gốc 3.
      - Pop từ stack ([0, 1, 2, 3, 4, 5]): Pop 5 (onStack[5]=false), SCC [5]. Pop 4 (onStack[4]=false), SCC [5, 4]. Pop 3 (onStack[3]=false), SCC [5, 4, 3]. Dừng vì gặp 3.
      - Lưu SCC [5, 4, 3]. Kích thước 3 (> 1). In chu trình. scc_count=1, sccs = [[5, 4, 3]].
      - Trở về 2.
    - Sau tarjan_dfs(3), low[2] (ban đầu là 0) vẫn là 0 (vì min(0, low[3]) = min(0, 3) = 0). Lưu ý cạnh 2->3 là cạnh từ SCC {0,1,2} sang SCC {3,4,5}, nó đã hoàn thành, nên onStack[3] đã false. Cạnh 2->3 không làm thay đổi low[2] thành 3.
    - Đỉnh 2 không còn kề (trừ 0 và 3). low[2] (0) == dfn[2] (2)? SAI. low[2] là 0, dfn[2] là 2. Điều kiện low[u] == dfn[u] chưa đúng. Điều này có vẻ không đúng với phân tích lý thuyết. Tại sao low[2] lại là 0? Ah, là do cạnh 2 -> 0.
    - Let's retrace 2: dfn[2]=2, low[2]=2. Cạnh 2 -> 0 (dfn[0]=0, onStack[0]=true): low[2] = min(low[2], dfn[0]) = min(2, 0) = 0. Cạnh 2 -> 3 (dfn[3]=3, onStack[3]=false): Bỏ qua vì 3 không on stack. Sau khi duyệt hết kề của 2, low[2] là 0. low[2] (0) != dfn[2] (2). Chưa phát hiện SCC tại 2. Trở về 1.
  - Sau tarjan_dfs(2), low[1] = min(low[1], low[2]) = min(1, 0) = 0.
  - Đỉnh 1 không còn kề (trừ 2). low[1] (0) != dfn[1] (1). Trở về 0.
- Sau tarjan_dfs(1), low[0] = min(low[0], low[1]) = min(0, 0) = 0.
- Đỉnh 0 không còn kề (trừ 1). low[0] (0) == dfn[0] (0). Phát hiện SCC tại gốc 0.
- Pop từ stack ([0, 1, 2]): Pop 2 (onStack[2]=false), SCC [2]. Pop 1 (onStack[1]=false), SCC [2, 1]. Pop 0 (onStack[0]=false), SCC [2, 1, 0]. Dừng.
- Lưu SCC [2, 1, 0]. Kích thước 3 (> 1). In chu trình. scc_count=2, sccs = [[5, 4, 3], [2, 1, 0]].
- tarjan_dfs(0) kết thúc.
Vòng lặp chính. Các đỉnh 1, 2, 3, 4, 5 đều đã thăm.
Kết thúc find_sccs.

Kết quả output sẽ in ra hai SCC, mỗi SCC có kích thước 3, và thông báo phát hiện chu trình cho cả hai SCC đó. Thứ tự xuất hiện của các SCC trong sccs có thể khác nhau tùy thuộc vào thứ tự pop stack.

Ví Dụ 3: Đồ thị không có chu trình (DAG)

Xét đồ thị với 4 đỉnh (0-3) và các cạnh: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3.

Đây là một đồ thị có hướng không có chu trình (DAG - Directed Acyclic Graph). Ta kỳ vọng thuật toán sẽ tìm ra 4 SCC, mỗi SCC chỉ chứa một đỉnh và không có cạnh khuyên.

// Sử dụng các hàm đã định nghĩa ở trên

int main() {
    cout << "--- Ví dụ 3: Đồ thị không có chu trình (DAG) ---" << endl;
    int n3 = 4;
    reset_graph(n3);

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
    add_edge(2, 3);

    find_sccs(n3);

    cout << "Tổng số SCC tìm được: " << scc_count << endl;
     cout << "Các SCC: " << endl;
     for(const auto& scc : sccs) {
        cout << "[";
        for(size_t i = 0; i < scc.size(); ++i) {
            cout << scc[i] << (i == scc.size() - 1 ? "" : ", ");
        }
        cout << "]" << endl;
    }
    cout << endl;

    return 0;
}

Phân tích Ví dụ 3:

find_sccs(4) được gọi. Khởi tạo. timer=0.
Bắt đầu DFS từ 0:
- tarjan_dfs(0): dfn[0]=low[0]=0, timer=1. Stack: [0], onStack[0]=true.
- 0 -> 1: dfn[1] == -1. Gọi tarjan_dfs(1).
  - tarjan_dfs(1): dfn[1]=low[1]=1, timer=2. Stack: [0, 1], onStack[1]=true.
  - 1 -> 3: dfn[3] == -1. Gọi tarjan_dfs(3).
    - tarjan_dfs(3): dfn[3]=low[3]=3, timer=3. Stack: [0, 1, 3], onStack[3]=true.
    - Đỉnh 3 không có đỉnh kề. low[3] (3) == dfn[3] (3). Phát hiện SCC tại 3.
    - Pop 3. Stack [0, 1]. onStack[3]=false. SCC: [3]. Kích thước 1, không cạnh khuyên. Không in chu trình. scc_count=1, sccs=[[3]].
    - Trở về 1.
  - Sau tarjan_dfs(3), low[1] = min(low[1], low[3]) = min(1, 3) = 1. (Không cập nhật vì low[3] lớn hơn low[1]).
  - Đỉnh 1 không còn kề (trừ 3 đã thăm). low[1] (1) == dfn[1] (1). Phát hiện SCC tại 1.
  - Pop 1. Stack [0]. onStack[1]=false. SCC: [1]. Kích thước 1, không cạnh khuyên. Không in chu trình. scc_count=2, sccs=[[3], [1]].
  - Trở về 0.
- Sau tarjan_dfs(1), low[0] = min(low[0], low[1]) = min(0, 1) = 0.
- 0 -> 2: dfn[2] == -1. Gọi tarjan_dfs(2).
  - tarjan_dfs(2): dfn[2]=low[2]=3, timer=4. Stack: [0, 2], onStack[2]=true. (Lưu ý: timer lúc này là 4, nên dfn[2] là 3).
  - 2 -> 3: dfn[3] == 2 (sai, dfn[3] = 3 từ trước), onStack[3] là false. Bỏ qua cạnh này khi cập nhật low[2].
  - Đỉnh 2 không còn kề (trừ 3). low[2] (3) == dfn[2] (3). Phát hiện SCC tại 2.
  - Pop 2. Stack [0]. onStack[2]=false. SCC: [2]. Kích thước 1, không cạnh khuyên. Không in chu trình. scc_count=3, sccs=[[3], [1], [2]].
  - Trở về 0.
- Sau tarjan_dfs(2), low[0] = min(low[0], low[2]) = min(0, 3) = 0.
- Đỉnh 0 không còn kề. low[0] (0) == dfn[0] (0). Phát hiện SCC tại 0.
- Pop 0. Stack rỗng. onStack[0]=false. SCC: [0]. Kích thước 1, không cạnh khuyên. Không in chu trình. scc_count=4, sccs=[[3], [1], [2], [0]].
- tarjan_dfs(0) kết thúc.
Vòng lặp chính. Tất cả đỉnh đã thăm.
Kết thúc find_sccs.

Kết quả output sẽ in ra 4 SCC, mỗi SCC chứa một đỉnh duy nhất ([3], [1], [2], [0]). Không có thông báo phát hiện chu trình vì không có SCC nào có kích thước lớn hơn 1 hoặc cạnh khuyên. Thứ tự các SCC có thể khác nhau.

Lưu ý về thứ tự các đỉnh trong SCC được in ra: Chúng được pop từ stack, nên thứ tự là từ đỉnh được thăm sau cùng trong SCC đến gốc của SCC đó. Ví dụ, trong SCC {0, 1, 2}, đỉnh 2 được thăm cuối cùng trong nhánh DFS dẫn đến SCC đó trước khi quay về gốc 0, nên nó sẽ được pop trước.

Bài tập ví dụ:

Điểm cao nhất

Là một nhân viên giỏi trong lĩnh vực phân tích dữ liệu, FullHouse Dev được giao nhiệm vụ phân tích một trò chơi đặc biệt. Họ cần tính toán điểm số tối đa có thể đạt được khi di chuyển qua các phòng được kết nối bởi các đường hầm.

Bài toán

Trò chơi gồm \(n\) phòng và \(m\) đường hầm. Điểm số ban đầu là 0, và mỗi khi đi qua một đường hầm, điểm số sẽ tăng thêm \(x\) (x có thể là số dương hoặc âm). Bạn có thể đi qua một đường hầm nhiều lần. Nhiệm vụ là đi từ phòng 1 đến phòng \(n\) và đạt được điểm số cao nhất có thể.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng phòng và số lượng đường hầm. Các phòng được đánh số từ \(1\) đến \(n\).
\(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(x\): đường hầm bắt đầu từ phòng \(a\), kết thúc ở phòng \(b\), và làm tăng điểm số thêm \(x\). Tất cả đường hầm đều là một chiều.

OUTPUT FORMAT:

In ra một số nguyên: điểm số cao nhất có thể đạt được. Tuy nhiên, nếu có thể đạt được điểm số vô hạn, in ra -1.

Ràng buộc:

\(1 \leq n \leq 2500\)
\(1 \leq m \leq 5000\)
\(1 \leq a,b \leq n\)
\(-10^9 \leq x \leq 10^9\)

Ví dụ

INPUT

OUTPUT

Giải thích

Có thể đạt được điểm số 5 bằng cách đi theo đường: 1 → 2 → 4 (3 + (-1) = 2) hoặc 1 → 3 → 4 (-2 + 7 = 5) hoặc đi thẳng từ 1 → 4 (4). Trong đó, đường đi 1 → 3 → 4 cho điểm số cao nhất là 5. Đây là hướng dẫn giải bài "Điểm cao nhất" bằng C++ một cách ngắn gọn:

Nhận dạng bài toán: Đây là bài toán tìm đường đi có tổng trọng số lớn nhất từ một đỉnh (1) đến một đỉnh khác (n) trong một đồ thị có hướng với trọng số trên cạnh có thể âm hoặc dương. Việc có thể đi qua đường hầm nhiều lần ngụ ý rằng đường đi có thể chứa chu trình. Nếu có một chu trình dương và có thể đi vào/thoát khỏi chu trình đó trên đường đến n, điểm số có thể là vô hạn.
Chuyển đổi bài toán: Tìm đường đi có tổng trọng số lớn nhất tương đương với tìm đường đi có tổng trọng số nhỏ nhất trên đồ thị với trọng số các cạnh bị đảo dấu (-x). Bài toán trở thành tìm đường đi ngắn nhất từ 1 đến n trong đồ thị có hướng với trọng số âm.
Chọn thuật toán: Thuật toán Bellman-Ford là phù hợp vì nó xử lý được trọng số âm và có thể phát hiện chu trình âm (tương ứng với chu trình dương trong bài toán gốc, dẫn đến điểm vô hạn).
Áp dụng Bellman-Ford:
- Khởi tạo mảng khoảng cách dist có kích thước n+1. dist[1] = 0, các dist[i] khác đặt là một giá trị rất lớn (vô cùng dương) để biểu thị không thể đến được hoặc chi phí rất cao. Sử dụng kiểu dữ liệu long long cho khoảng cách vì điểm có thể rất lớn.
- Biểu diễn đồ thị bằng danh sách cạnh, lưu trọng số đã bị đảo dấu (-x).
- Thực hiện lặp n-1 lần. Mỗi lần lặp, duyệt qua tất cả các cạnh (u, v) với trọng số -w: Nếu dist[u] không phải là vô cùng và dist[u] + (-w) < dist[v], cập nhật dist[v] = dist[u] + (-w). Sau n-1 lần lặp, nếu không có chu trình âm nào có thể ảnh hưởng đến đường đi đến n, dist[n] sẽ chứa chi phí nhỏ nhất từ 1 đến n.
Kiểm tra điểm vô hạn:
- Điểm vô hạn xảy ra nếu có một chu trình dương (chu trình âm trong đồ thị đảo dấu) có thể đến được từ đỉnh 1 VÀ từ chu trình đó có thể đến được đỉnh n.
- Sau khi thực hiện n-1 lần lặp Bellman-Ford, thực hiện thêm một lần lặp thứ n.
- Trong lần lặp thứ n, nếu có bất kỳ khoảng cách dist[v] nào có thể được cập nhật từ dist[u] + (-w) (dist[u] không phải vô cùng và dist[u] + (-w) < dist[v]), điều này cho thấy có một chu trình âm có thể đến được từ đỉnh 1 và ảnh hưởng đến đỉnh v.
- Để kiểm tra xem chu trình âm này có thể dẫn đến đỉnh n hay không, ta cần biết liệu đỉnh n có reachable từ đỉnh v đó (trong đồ thị gốc) hay không.
- Một cách hiệu quả để kiểm tra: Xây dựng đồ thị nghịch đảo (đảo chiều tất cả các cạnh). Thực hiện BFS hoặc DFS trên đồ thị nghịch đảo từ đỉnh n để đánh dấu tất cả các đỉnh u sao cho n có thể reachable từ u trong đồ thị gốc. Lưu lại các đỉnh này vào một tập/mảng boolean.
- Trong lần lặp thứ n của Bellman-Ford: Nếu một cạnh (u, v) với trọng số -w gây ra cập nhật dist[v], và đỉnh v được đánh dấu là có thể đến được đỉnh n (qua bước BFS/DFS trên đồ thị nghịch đảo), thì điểm số vô hạn là có thể. In -1 và dừng chương trình.
Kết quả:
- Nếu không phát hiện điểm vô hạn sau lần lặp thứ n, điểm số cao nhất có thể đạt được là -dist[n] (lấy đối của chi phí nhỏ nhất). In giá trị này.

Tóm tắt các bước:

Đọc n, m.
Lưu trữ các cạnh với trọng số đã đảo dấu (-x).
Khởi tạo mảng dist (long long), dist[1] = 0, còn lại là giá trị lớn.
Chạy Bellman-Ford n-1 lần lặp.
Xây dựng đồ thị nghịch đảo.
Chạy BFS/DFS từ n trên đồ thị nghịch đảo để đánh dấu các đỉnh có thể đến n trong đồ thị gốc.
Chạy Bellman-Ford lần lặp thứ n. Nếu một cập nhật dist[v] xảy ra và đỉnh v đã được đánh dấu ở bước 6, in -1 và kết thúc.
Nếu hoàn thành bước 7 mà không in -1, in -dist[n].

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

Comments

There are no comments at the moment.