Bài 23.5. Bài tập cơ bản về thuật toán Tarjan

Chào mừng 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ẽ khám phá một viên ngọc quý trong thế giới giải thuật đồ thị: Thuật toán Tarjan. Đây là một công cụ cực kỳ mạnh mẽ và thanh lịch để giải quyết bài toán tìm các Thành phần liên thông mạnh (Strongly Connected Components - SCC) trong một đồ thị có hướng chỉ với một lần duyệt Depth-First Search (DFS) duy nhất.

Nếu bạn đã từng làm việc với đồ thị có hướng, bạn biết rằng việc di chuyển giữa các đỉnh không phải lúc nào cũng "hai chiều" như đồ thị vô hướng. Chính sự "một chiều" này tạo nên khái niệm SCC: một tập hợp các đỉnh mà từ bất kỳ đỉnh nào trong tập hợp, ta đều có thể đi đến bất kỳ đỉnh nào khác trong cùng tập hợp bằng cách di chuyển theo hướng các cạnh.

Tại sao việc tìm SCC lại quan trọng? Chúng xuất hiện trong rất nhiều bài toán thực tế: phân tích mạng máy tính, giải quyết các phụ thuộc trong biên dịch chương trình, phân tích luồng dữ liệu, thậm chí trong các bài toán trên các mạng xã hội hay hệ thống phân phối. Thuật toán Tarjan cung cấp một cách hiệu quả để "phá vỡ" đồ thị có hướng thành các khối SCC này, giúp đơn giản hóa việc phân tích đồ thị tổng thể (chẳng hạn bằng cách xây dựng một đồ thị mới mà mỗi đỉnh là một SCC và các cạnh biểu diễn mối quan hệ giữa các SCC).

Thách thức và Tại sao Tarjan lại đặc biệt?

Việc tìm SCC không đơn giản chỉ là chạy DFS hoặc BFS thông thường. Một lần duyệt DFS có thể đi vào một SCC, nhưng không có cách nào dễ dàng để biết được khi nào bạn đã thăm hết toàn bộ SCC đó và sẵn sàng "kết thúc" nó. Các cạnh đi ra khỏi SCC có thể dẫn bạn đi lạc sang các phần khác của đồ thị.

Thuật toán Tarjan giải quyết vấn đề này bằng cách theo dõi thông tin quan trọng trong quá trình DFS: thời gian khám phá (discovery time) và giá trị low-link (low-link value) cho mỗi đỉnh. Hơn nữa, nó sử dụng một ngăn xếp (stack) để giữ lại các đỉnh có thể thuộc về SCC hiện tại đang được xét.

Điểm mấu chốt của Tarjan nằm ở cách nó sử dụng và cập nhật giá trị low-link. Giá trị low[u] của đỉnh u về cơ bản là thời gian khám phá (discovery time) nhỏ nhất có thể đạt được từ đỉnh u (bao gồm cả u) thông qua các cạnh trong cây DFS hoặc qua tối đa một cạnh ngược (back-edge) hoặc cạnh chéo (cross-edge) dẫn đến một đỉnh hiện đang nằm trên ngăn xếp.

Khi thuật toán kết thúc việc duyệt DFS cho một đỉnh u và tất cả các đỉnh con của nó trong cây DFS, nếu low[u] == disc[u] (trong đó disc[u] là thời gian khám phá của u), điều đó có nghĩa là u là "gốc" của một SCC. Tất cả các đỉnh được khám phá kể từ khi u được đẩy vào ngăn xếp và vẫn còn nằm trên ngăn xếp tại thời điểm này chính là các đỉnh thuộc về SCC mà u là gốc.

Các Khái niệm Cốt lõi của Thuật toán Tarjan

Để hiểu rõ hơn, hãy đi sâu vào các thành phần chính:

Thời gian Khám phá (disc[u]): Đây là thời điểm (bước thứ tự của bộ đếm thời gian) mà đỉnh u được thăm lần đầu tiên trong quá trình DFS. Ban đầu, tất cả disc được gán giá trị đặc biệt (thường là -1) để đánh dấu là chưa thăm.
Giá trị Low-Link (low[u]): Như đã giải thích ở trên, đây là thời gian khám phá nhỏ nhất có thể đạt được từ u (bao gồm u) thông qua cây DFS và tối đa một cạnh quay lại hoặc cạnh chéo đến một đỉnh đang còn trên ngăn xếp*.
Ngăn xếp (Stack): Lưu trữ các đỉnh theo thứ tự chúng được thăm trong DFS. Các đỉnh này có khả năng thuộc về SCC hiện tại đang được xây dựng.
Cờ onStack[u]: Một mảng boolean đánh dấu xem đỉnh u có đang nằm trên ngăn xếp hay không. Điều này cực kỳ quan trọng để phân biệt giữa cạnh ngược/chéo đến đỉnh trên stack (có liên quan đến SCC hiện tại) và cạnh đến đỉnh đã ra khỏi stack (đã thuộc về một SCC khác).
Bộ đếm thời gian (timer): Một biến toàn cục tăng dần mỗi khi một đỉnh mới được khám phá, dùng để gán giá trị cho disc.
Bộ đếm SCC (sccCount): Biến đếm số lượng SCC tìm được.
Lưu trữ SCCs: Một cách để lưu trữ các SCC tìm được (ví dụ: vector các vector).

Cơ chế hoạt động của Thuật thuật Tarjan (Chi tiết)

Hãy xem xét hàm DFS chính tarjanDFS(u) xử lý đỉnh u:

Khi bắt đầu thăm đỉnh u:
- Gán disc[u] và low[u] bằng giá trị hiện tại của bộ đếm thời gian timer, sau đó tăng timer lên.
- Đẩy đỉnh u vào ngăn xếp và đánh dấu onStack[u] = true.
Duyệt qua tất cả các đỉnh v là hàng xóm của u (có cạnh từ u đến v):
- Nếu v chưa được thăm (nghĩa là disc[v] == -1):
  - Điều này có nghĩa v là con của u trong cây DFS hiện tại.
  - Gọi đệ quy tarjanDFS(v).
  - Sau khi lời gọi đệ quy trả về, cập nhật low[u] = min(low[u], low[v]). Điều này là để "lan truyền" giá trị low-link nhỏ nhất từ cây con của v lên đỉnh u. Nếu có đường đi từ cây con của v tới một đỉnh có disc nhỏ hơn disc[u] (và đỉnh đó còn trên stack), thì đường đi đó cũng coi như đi được từ u.
- Nếu v đã được thăm (nghĩa là disc[v] != -1) VÀ v vẫn còn trên ngăn xếp (onStack[v] == true):
  - Đây là trường hợp có một cạnh ngược hoặc cạnh chéo từ u đến v. Vì v vẫn còn trên ngăn xếp, v thuộc về SCC hiện tại đang được xem xét (hoặc là tổ tiên của u trong cây DFS).
  - Cập nhật low[u] = min(low[u], disc[v]). Lưu ý quan trọng: Chúng ta dùng disc[v] chứ không phải low[v]. Lý do là cạnh u -> v cho phép chúng ta đạt đến v (có thời gian khám phá disc[v]). Mọi đỉnh có thời gian khám phá nhỏ hơn disc[v] mà v có thể đạt tới thông qua các cạnh khác (thể hiện qua low[v]) thì chúng ta cũng đã xét đến khi tính low[v] rồi. Việc dùng disc[v] đảm bảo chúng ta chỉ xem xét đường đi trực tiếp đến v hoặc tổ tiên của v thông qua cạnh u -> v, và rằng đỉnh v (hoặc tổ tiên của nó) là một phần của "lộ trình" hiện tại (vì nó còn trên stack).
- Nếu v đã được thăm VÀ v không còn trên ngăn xếp (onStack[v] == false):
  - Cạnh u -> v dẫn đến một đỉnh đã thuộc về một SCC khác đã được xác định và "bóc" ra khỏi stack. Cạnh này không liên quan đến việc xác định low[u] cho SCC hiện tại. Chúng ta bỏ qua cạnh này trong việc cập nhật low[u].
Sau khi đã duyệt qua tất cả hàng xóm của u và lời gọi đệ quy đã trả về:
- Kiểm tra điều kiện low[u] == disc[u]: Nếu đúng, đỉnh u là gốc của một SCC.
- Bóc các đỉnh ra khỏi ngăn xếp bắt đầu từ đỉnh trên cùng cho đến khi gặp đỉnh u. Tất cả các đỉnh được bóc ra này (bao gồm cả u) tạo thành một Thành phần liên thông mạnh (SCC).
- Đối với mỗi đỉnh w được bóc ra, đánh dấu onStack[w] = false.
- Lưu trữ SCC vừa tìm được và tăng bộ đếm sccCount.

Quá trình này được lặp lại cho tất cả các đỉnh của đồ thị bằng cách gọi hàm DFS chính cho mọi đỉnh chưa được thăm (disc[i] == -1).

Ví dụ Minh họa 1: Đồ thị Đơn giản

Hãy xem xét đồ thị có hướng sau với 4 đỉnh (0, 1, 2, 3) và các cạnh: (0, 1), (1, 2), (2, 0), (1, 3).

Đồ thị:

0 --> 1 --> 2
^     |     |
|     v     v
|     3     0 (cạnh ngược)
|           ^
+-----------+

(Visual: Node 0 nối đến 1, 1 đến 2, 2 đến 0 tạo thành một chu trình. Node 1 nối đến 3.)

Chúng ta sẽ theo dõi quá trình Tarjan bắt đầu từ đỉnh 0. Khởi tạo: disc và low là -1 cho tất cả các đỉnh. Ngăn xếp rỗng. onStack là false cho tất cả. timer = 0.

Gọi tarjanDFS(0):
- disc[0] = 0, low[0] = 0. timer = 1.
- Đẩy 0 vào stack: [0]. onStack[0] = true.
- Duyệt hàng xóm của 0:
  - Hàng xóm 1: disc[1] == -1. Gọi tarjanDFS(1).
    - tarjanDFS(1): disc[1] = 1, low[1] = 1. timer = 2.
    - Đẩy 1 vào stack: [0, 1]. onStack[1] = true.
    - Duyệt hàng xóm của 1:
      - Hàng xóm 2: disc[2] == -1. Gọi tarjanDFS(2).
        
        tarjanDFS(2): disc[2] = 2, low[2] = 2. timer = 3.
        
        Đẩy 2 vào stack: [0, 1, 2]. onStack[2] = true.
        
        Duyệt hàng xóm của 2:
        
        * Hàng xóm 0: disc[0] == 0, onStack[0] == true. Đây là cạnh ngược/chéo đến đỉnh trên stack. Cập nhật low[2] = min(low[2], disc[0]) = min(2, 0) = 0.
        
        Hết hàng xóm của 2. Kiểm tra điều kiện SCC: low[2] == disc[2]? 0 == 2? False.
        
        Trả về từ tarjanDFS(2).
      - Trở lại tarjanDFS(1): low[1] = min(low[1], low[2]) = min(1, 0) = 0.
      - Hàng xóm 3: disc[3] == -1. Gọi tarjanDFS(3).
        
        tarjanDFS(3): disc[3] = 3, low[3] = 3. timer = 4.
        
        Đẩy 3 vào stack: [0, 1, 2, 3]. onStack[3] = true.
        
        Hết hàng xóm của 3. Kiểm tra điều kiện SCC: low[3] == disc[3]? 3 == 3? True. Tìm thấy một SCC!
        
        Bóc stack cho đến 3: Pop 3. SCC = {3}. onStack[3] = false. Stack: [0, 1, 2]. sccCount = 1.
        
        Trả về từ tarjanDFS(3).
      - Trở lại tarjanDFS(1): low[1] = min(low[1], low[3]) = min(0, 3) = 0. (low[3] không ảnh hưởng vì nó đã được xử lý thành SCC riêng).
    - Hết hàng xóm của 1. Kiểm tra điều kiện SCC: low[1] == disc[1]? 0 == 1? False.
    - Trả về từ tarjanDFS(1).
  - Trở lại tarjanDFS(0): low[0] = min(low[0], low[1]) = min(0, 0) = 0.
- Hết hàng xóm của 0. Kiểm tra điều kiện SCC: low[0] == disc[0]? 0 == 0? True. Tìm thấy một SCC!
- Bóc stack cho đến 0: Pop 2, Pop 1, Pop 0. SCC = {2, 1, 0}. onStack[2]=false, onStack[1]=false, onStack[0]=false. Stack: []. sccCount = 2.
- Trả về từ tarjanDFS(0).
Vòng lặp chính kiểm tra các đỉnh khác (1, 2, 3). Tất cả đều đã có disc != -1.

Kết quả: Tìm thấy 2 SCCs: {3} và {0, 1, 2}. Kết quả này khớp với phân tích đồ thị ban đầu.

Cài đặt Thuật toán Tarjan bằng C++

Đây là đoạn mã C++ minh họa thuật toán Tarjan:

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

// Kích thước đồ thị tối đa (hoặc đủ lớn)
const int MAXN = 1005;

std::vector<int> adj[MAXN]; // Danh sách kề biểu diễn đồ thị
int disc[MAXN];            // Thời gian khám phá (discovery time)
int low[MAXN];             // Giá trị low-link
bool onStack[MAXN];        // Đánh dấu đỉnh có đang trên ngăn xếp không
std::stack<int> st;        // Ngăn xếp dùng cho Tarjan

int timer;                 // Bộ đếm thời gian
int sccCount;              // Số lượng SCC tìm được

// Vector để lưu trữ các SCC tìm được
std::vector<std::vector<int>> sccs;

// Hàm DFS chính của thuật toán Tarjan
void tarjanDFS(int u) {
    // Bước 1: Khởi tạo khi thăm lần đầu
    disc[u] = low[u] = timer++;
    st.push(u);
    onStack[u] = true;

    // Bước 2: Duyệt qua các đỉnh kề của u
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            // v chưa được thăm -> Duyệt tiếp xuống cây con
            tarjanDFS(v);
            // Cập nhật low[u] từ low[v]
            low[u] = std::min(low[u], low[v]);
        } else if (onStack[v]) {
            // v đã được thăm và đang trên ngăn xếp
            // Đây là cạnh ngược hoặc cạnh chéo đến đỉnh trên stack
            // Cập nhật low[u] dựa vào disc[v]
            low[u] = std::min(low[u], disc[v]);
        }
        // Else: v đã thăm nhưng không trên stack -> Bỏ qua (thuộc SCC khác đã xử lý)
    }

    // Bước 3: Kiểm tra điều kiện tìm thấy SCC
    if (low[u] == disc[u]) {
        // u là gốc của một SCC
        std::vector<int> currentSCC;
        while (true) {
            int w = st.top();
            st.pop();
            onStack[w] = false;
            currentSCC.push_back(w);

            if (w == u) {
                break; // Đã bóc đến đỉnh u
            }
        }
        // Lưu trữ SCC vừa tìm được
        sccs.push_back(currentSCC);
        sccCount++;
    }
}

// Hàm chính để chạy Tarjan trên toàn bộ đồ thị
void findSCCs(int V) {
    // Khởi tạo mảng disc, low, onStack
    for (int i = 0; i < V; ++i) {
        disc[i] = -1;
        low[i] = -1;
        onStack[i] = false;
    }

    timer = 0;
    sccCount = 0;
    sccs.clear(); // Xóa kết quả cũ nếu có

    // Duyệt qua tất cả các đỉnh. Nếu đỉnh chưa thăm, bắt đầu một DFS mới từ đó.
    for (int i = 0; i < V; ++i) {
        if (disc[i] == -1) {
            tarjanDFS(i);
        }
    }
}

int main() {
    int V, E; // V: số đỉnh, E: số cạnh

    std::cout << "Nhap so luong dinh va so luong canh: ";
    std::cin >> V >> E;

    // Xóa danh sách kề cũ (nếu có nhiều test case)
    for(int i = 0; i < V; ++i) {
        adj[i].clear();
    }

    std::cout << "Nhap cac canh (u v, dinh tu 0 den V-1):\n";
    for (int i = 0; i < E; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
    }

    findSCCs(V);

    std::cout << "\nTim thay " << sccCount << " Thanh phan lien thong manh (SCC):\n";
    for (const auto& scc : sccs) {
        std::cout << "{ ";
        for (size_t i = 0; i < scc.size(); ++i) {
            std::cout << scc[i] << (i == scc.size() - 1 ? "" : ", ");
        }
        std::cout << " }\n";
    }

    return 0;
}

Giải thích Code C++

Khai báo biến toàn cục:
- adj[MAXN]: Mảng các vector để lưu đồ thị dưới dạng danh sách kề. MAXN là kích thước tối đa của đồ thị bạn định xử lý.
- disc[MAXN], low[MAXN]: Mảng lưu thời gian khám phá và giá trị low-link cho mỗi đỉnh.
- onStack[MAXN]: Mảng boolean để kiểm tra xem đỉnh có đang trên stack không.
- st: Ngăn xếp chuẩn của C++ (std::stack) để thực hiện chức năng stack của Tarjan.
- timer: Biến đếm thời gian, dùng để gán giá trị cho disc.
- sccCount: Biến đếm số SCC tìm được.
- sccs: Vector các vector để lưu trữ kết quả, mỗi vector con là một SCC.
Hàm tarjanDFS(int u):
- Đây là trái tim của thuật toán, thực hiện quá trình DFS và tính toán disc, low.
- disc[u] = low[u] = timer++;: Khi thăm đỉnh u lần đầu, gán thời gian khám phá và low-link ban đầu bằng giá trị timer hiện tại, sau đó tăng timer.
- st.push(u); onStack[u] = true;: Đẩy u vào stack và đánh dấu nó đang trên stack.
- Vòng lặp for (int v : adj[u]): Duyệt qua các đỉnh v mà có cạnh từ u đến v.
  - if (disc[v] == -1): Nếu v chưa được thăm, gọi đệ quy tarjanDFS(v). Sau khi trở về, low[u] = std::min(low[u], low[v]) cập nhật low[u] dựa trên giá trị low-link nhỏ nhất có thể đạt được từ cây con của v.
  - else if (onStack[v]): Nếu v đã thăm và đang trên stack. Đây là cạnh ngược hoặc cạnh chéo đến một tổ tiên hoặc một đỉnh cùng SCC đang được xử lý. low[u] = std::min(low[u], disc[v]) cập nhật low[u] dựa trên thời gian khám phá của v. Lưu ý lại lần nữa: dùng disc[v] chứ không phải low[v].
- if (low[u] == disc[u]): Sau khi duyệt hết các hàng xóm và các lời gọi đệ quy con đã trả về, kiểm tra điều kiện này. Nếu đúng, u là gốc của một SCC.
- Vòng while (true) bên trong khối if: Bóc các đỉnh từ stack ra cho đến khi gặp u. Các đỉnh này tạo thành một SCC. Đánh dấu onStack của chúng là false. Lưu trữ SCC này.
Hàm findSCCs(int V):
- Hàm này chuẩn bị các mảng và biến (disc, low, onStack, timer, sccCount, sccs).
- Vòng lặp for (int i = 0; i < V; ++i): Đảm bảo rằng chúng ta bắt đầu quá trình DFS từ mọi đỉnh chưa được thăm. Điều này là cần thiết để xử lý các đồ thị có hướng có nhiều thành phần liên thông yếu (weakly connected components). Nếu một đỉnh chưa được thăm, nó thuộc về một SCC chưa được tìm thấy.
Hàm main():
- Đọc số đỉnh V và số cạnh E.
- Đọc các cạnh và xây dựng danh sách kề adj.
- Gọi findSCCs(V) để chạy thuật toán.
- In ra số lượng SCC và liệt kê các đỉnh trong mỗi SCC tìm được.

Ví dụ Minh họa 2: Đồ thị Phức tạp hơn

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

0 --> 1 --> 2
^     |     |
|     v     v
+-----+-+---0 (cạnh ngược)
      | v
      3 --> 4 --> 6
      ^     |
      |     v
      +-----5

(Visual: {0,1,2} tạo thành một chu trình. 1 nối sang 3. {3,4,5} tạo thành một chu trình. 4 nối sang 6.)

Các SCCs trong đồ thị này là: {0, 1, 2}, {3, 4, 5}, {6}. Hãy chạy code với input này: 7 8 0 1 1 2 2 0 1 3 3 4 4 5 5 3 4 6

Output sẽ tương tự như:

Nhap so luong dinh va so luong canh: 7 8
Nhap cac canh (u v, dinh tu 0 den V-1):
0 1
1 2
2 0
1 3
3 4
4 5
5 3
4 6

Tim thay 3 Thanh phan lien thong manh (SCC):
{ 6 }
{ 3, 4, 5 }
{ 0, 1, 2 }

Thứ tự các SCC được in ra có thể khác nhau (phụ thuộc vào thứ tự thăm DFS và thứ tự cạnh trong danh sách kề), nhưng các đỉnh trong mỗi SCC sẽ đúng.

Nếu bắt đầu từ 0: Thuật toán sẽ tìm thấy SCC {0, 1, 2} đầu tiên khi tarjanDFS(0) kết thúc.
Nếu bắt đầu từ 3 (sau khi 0,1,2 đã được xử lý): Thuật toán sẽ đi 3 -> 4 -> 5 -> 3. Khi DFS quay lại 3, low[3] sẽ được cập nhật nhỏ xuống đến disc của một đỉnh trên chu trình 3-4-5. Khi tarjanDFS(3) kết thúc và low[3] == disc[3], SCC {3, 4, 5} sẽ được bóc ra.
Nếu bắt đầu từ 6 (sau khi các thành phần khác đã được xử lý hoặc trong một nhánh DFS khác): 6 không có cạnh đi ra. low[6] sẽ bằng disc[6]. Khi tarjanDFS(6) kết thúc, SCC {6} sẽ được bóc ra.
Lưu ý cạnh (4, 6): Khi thăm 4, nó có cạnh đến 6. Nếu 6 chưa thăm, gọi đệ quy tarjanDFS(6). Sau khi tarjanDFS(6) hoàn thành và bóc SCC {6} ra khỏi stack, khi trở lại tarjanDFS(4), cạnh (4,6) sẽ được coi là cạnh đi đến đỉnh đã thăm nhưng không còn trên stack (onStack[6] là false). Do đó, cạnh này không ảnh hưởng đến việc cập nhật low[4], và SCC {3, 4, 5} được xác định độc lập với SCC {6}.

Độ phức tạp của thuật toán Tarjan là O(V + E), trong đó V là số đỉnh và E là số cạnh, vì nó chỉ thực hiện một lần duyệt DFS trên đồ thị. Điều này làm cho nó trở thành một trong những giải thuật hiệu quả nhất để tìm SCC.

Bài tập ví dụ:

Tìm chu trình

Trong một dự án cơ khí mới, FullHouse Dev được giao nhiệm vụ phân tích một hệ thống máy móc phức tạp. Họ cần kiểm tra xem liệu có tồn tại chu trình âm trong sơ đồ kết nối của hệ thống hay không, để đảm bảo tính ổn định của toàn bộ hệ thống.

Bài toán

Cho một đồ thị có hướng, nhiệm vụ của bạn là tìm ra xem đồ thị có chứa chu trình âm hay không, và đưa ra một ví dụ về chu trình đó nếu có.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng đỉnh và cạnh. Các đỉnh được đánh số từ \(1,2,\ldots,n\).
\(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): mô tả một cạnh từ đỉnh \(a\) đến đỉnh \(b\) với độ dài \(c\).

OUTPUT FORMAT:

Nếu đồ thị chứa chu trình âm, in ra "YES" và các đỉnh trong chu trình theo đúng thứ tự.
Nếu có nhiều chu trình âm, bạn có thể in ra bất kỳ chu trình nào.
Nếu không có chu trình âm, in ra "NO".

Ràng buộc:

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

Ví dụ

INPUT

OUTPUT

YES
1 2 4 1

Giải thích

Trong ví dụ này, chu trình 1 → 2 → 4 → 1 có tổng độ dài là 1 + 1 + (-3) = -1 < 0, do đó đây là một chu trình âm. Đây là hướng dẫn giải bài toán "Tìm chu trình âm" sử dụng thuật toán Bellman-Ford.

Ý tưởng chính:

Bài toán tìm chu trình âm trong đồ thị có hướng với trọng số cạnh có thể âm là một ứng dụng kinh điển của thuật toán Bellman-Ford.

Thuật toán Bellman-Ford tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số cạnh âm (nhưng không có chu trình âm). Nếu đồ thị chứa chu trình âm, Bellman-Ford sẽ phát hiện ra điều đó.

Cách phát hiện chu trình âm bằng Bellman-Ford:

Thuật toán Bellman-Ford thực hiện N-1 lượt lặp (với N là số đỉnh). Trong mỗi lượt, nó duyệt qua tất cả các cạnh và "thư giãn" chúng. Thao tác thư giãn cạnh (u, v) với trọng số w là kiểm tra xem dist[u] + w < dist[v] có đúng không. Nếu có, cập nhật dist[v] = dist[u] + w và lưu lại đỉnh trước của v là u (để sau này truy vết).
Sau N-1 lượt lặp, mảng dist chứa độ dài đường đi ngắn nhất từ nguồn đến các đỉnh khác (nếu không có chu trình âm).
Nếu đồ thị chứa chu trình âm, thì sau N-1 lượt lặp, vẫn sẽ có ít nhất một cạnh có thể được "thư giãn" (nghĩa là dist[u] + w < dist[v] vẫn đúng). Điều này xảy ra vì đi qua chu trình âm làm giảm tổng trọng số đường đi vô hạn.
Để tìm bất kỳ chu trình âm nào trong đồ thị (không chỉ những chu trình reachable từ một nguồn cụ thể), ta có thể thực hiện N lượt lặp thay vì N-1. Nếu trong lượt lặp thứ N, vẫn có cạnh được thư giãn, thì đồ thị chắc chắn có chu trình âm. Đỉnh v của bất kỳ cạnh (u, v) nào được thư giãn trong lượt lặp thứ N này chắc chắn nằm trên hoặc có thể đi đến từ một chu trình âm.

Các bước giải:

Khởi tạo:
- Sử dụng mảng dist (kiểu long long để tránh tràn số) kích thước N+1, khởi tạo tất cả giá trị bằng 0 (hoặc một giá trị đủ lớn coi như vô cùng dương, nhưng khởi tạo 0 đơn giản hơn cho việc phát hiện chu trình âm bất kỳ).
- Sử dụng mảng parent (kiểu int) kích thước N+1, khởi tạo tất cả giá trị bằng -1 để lưu đỉnh trước trong đường đi.
- Lưu trữ danh sách các cạnh.
Chạy thuật toán Bellman-Ford:
- Lặp N lần (từ 1 đến N).
- Trong mỗi lần lặp:
  - Duyệt qua tất cả M cạnh (u, v, w).
  - Nếu dist[u] + w < dist[v]:
    - Cập nhật dist[v] = dist[u] + w.
    - Cập nhật parent[v] = u.
    - Nếu đang ở lần lặp thứ N, đánh dấu đỉnh v này (ví dụ: lưu vào biến negative_cycle_node) vì nó là đỉnh nằm trên hoặc reachable từ một chu trình âm.
Kiểm tra và truy vết chu trình âm:
- Sau N lần lặp, kiểm tra nếu có đỉnh nào được đánh dấu (negative_cycle_node != -1).
- Nếu không có đỉnh nào được đánh dấu: In ra "NO".
- Nếu có đỉnh được đánh dấu (negative_cycle_node): In ra "YES".
  - Để truy vết chu trình: Bắt đầu từ đỉnh negative_cycle_node. Đi ngược về N lần theo mảng parent (ví dụ: curr = parent[curr] lặp N lần). Đỉnh cuối cùng thu được sau N bước ngược này chắc chắn nằm trên chu trình âm. Gán đỉnh này vào biến start_node_on_cycle.
  - Tiếp tục đi ngược từ start_node_on_cycle theo mảng parent, đồng thời lưu các đỉnh vào một danh sách/vector, cho đến khi gặp lại start_node_on_cycle.
  - Danh sách các đỉnh thu được chính là chu trình âm (theo thứ tự ngược). Đảo ngược danh sách và in ra.

Lưu ý:

Sử dụng kiểu dữ liệu long long cho mảng dist và trọng số cạnh để tránh tràn số, vì tổng trọng số trên một đường đi có thể rất lớn hoặc rất bé.
Việc đi ngược N bước từ negative_cycle_node đảm bảo rằng bạn sẽ "nhảy" vào chu trình âm nếu đỉnh đó chỉ reachable từ chu trình âm chứ không trực tiếp nằm trên nó.
Thời gian thực hiện của thuật toán là O(N * M).

Ví dụ truy vết chu trình (giả sử mảng parent):

Nếu negative_cycle_node = 4 và mảng parent sau N lượt lặp là: parent[1]=4, parent[2]=1, parent[3]=4, parent[4]=2. N=4.

Đi ngược N=4 bước từ 4:
- Bước 1: curr = parent[4] = 2
- Bước 2: curr = parent[2] = 1
- Bước 3: curr = parent[1] = 4
- Bước 4: curr = parent[4] = 2 Đỉnh start_node_on_cycle là 2.
Đi ngược từ 2, lưu vào vector cho đến khi gặp lại 2:
- vector: [2] ; curr = parent[2] = 1
- vector: [2, 1] ; curr = parent[1] = 4
- vector: [2, 1, 4] ; curr = parent[4] = 2
- Gặp lại 2. Dừng lại và thêm đỉnh cuối cùng vào vector: [2, 1, 4, 2].
Đảo ngược vector: [2, 4, 1, 2]. Đây là chu trình âm. In ra 2 4 1 2. (Lưu ý: trong ví dụ đề bài là 1 2 4 1, thứ tự có thể khác nhưng các đỉnh và cạnh là như nhau).

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

Comments

There are no comments at the moment.