Bài 23.1. Thuật toán Tarjan tìm thành phần liên thông mạnh

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 của FullhouseDev!

Trong thế giới của đồ thị, đặc biệt là đồ thị có hướng, việc hiểu rõ cấu trúc liên kết giữa các đỉnh là vô cùng quan trọng. Một trong những khái niệm cốt lõi giúp chúng ta phân tích đồ thị có hướng chính là Thành phần liên thông mạnh. Hôm nay, chúng ta sẽ khám phá một "vũ khí" cực kỳ mạnh mẽ để tìm ra các thành phần này: Thuật toán Tarjan.

Thuật toán Tarjan, được đặt tên theo nhà khoa học máy tính Robert Tarjan, là một trong những phương pháp hiệu quả và thanh lịch nhất để tìm tất cả các Thành phần liên thông mạnh (SCC) trong một đồ thị có hướng chỉ với một lần duyệt DFS duy nhất.

Thành phần liên thông mạnh (Strongly Connected Component - SCC) là gì?

Trước khi đi sâu vào thuật toán, hãy làm rõ khái niệm SCC.

Một Thành phần liên thông mạnh (SCC) của một đồ thị có hướng là một tập hợp con các đỉnh sao cho với bất kỳ hai đỉnh u và v nào trong tập hợp con này, đều tồn tại một đường đi từ u đến v và một đường đi từ v đến u. Nói cách khác, mọi đỉnh trong SCC đều có thể "đi tới" và "quay về" mọi đỉnh khác trong cùng SCC đó.

Các SCC tạo thành một phân hoạch các đỉnh của đồ thị. Điều thú vị là nếu chúng ta thu gọn mỗi SCC thành một "siêu đỉnh" (supernode), đồ thị mới tạo thành sẽ là một Đồ thị không chu trình có hướng (Directed Acyclic Graph - DAG). Điều này có ứng dụng rất lớn trong việc phân tích cấu trúc của đồ thị có hướng phức tạp.

Ví dụ đơn giản:

Xét đồ thị với các đỉnh A, B, C, D, E và các cạnh: A->B, B->C, C->A, C->D, D->E, E->D.

A, B, C tạo thành một SCC vì A có thể đi tới B, C và ngược lại.
D, E tạo thành một SCC vì D có thể đi tới E và ngược lại.
Có một cạnh từ SCC {A, B, C} sang SCC {D, E} (cạnh C->D).

Tại sao cần tìm Thành phần liên thông mạnh?

Việc tìm SCC có nhiều ứng dụng thực tế, bao gồm:

Phân tích phụ thuộc: Trong các hệ thống phụ thuộc (ví dụ: các module phần mềm, các tác vụ trong một dự án), các SCC biểu thị các nhóm các mục phụ thuộc lẫn nhau theo chu kỳ. Điều này giúp xác định các điểm tắc nghẽn hoặc vấn đề tiềm ẩn.
Kiểm chứng mô hình (Model Checking): Trong các hệ thống trạng thái hữu hạn, SCC có thể biểu diễn các trạng thái mà hệ thống có thể ở lại vô thời hạn.
Phân tích mạng xã hội: Tìm các nhóm người dùng có liên kết chặt chẽ với nhau theo cả hai chiều.
Trình biên dịch: Phát hiện các vòng lặp phụ thuộc giữa các hàm hoặc các biến.

Với tầm quan trọng như vậy, việc có một thuật toán hiệu quả để tìm SCC là điều thiết yếu. Và đó chính là lúc Tarjan tỏa sáng!

Thuật toán Tarjan: Giải mã sự tinh tế

Thuật toán Tarjan dựa trên ý tưởng mở rộng của duyệt đồ thị theo chiều sâu (DFS). Nó sử dụng một số biến và cấu trúc dữ liệu bổ trợ để theo dõi thông tin trong quá trình DFS, giúp nhận diện ranh giới của từng SCC.

Các yếu tố cốt lõi của Tarjan bao gồm:

Duyệt DFS: Thuật toán duyệt toàn bộ đồ thị bằng DFS.
disc (Discovery time): Một mảng ghi lại "thời điểm khám phá" (discovery time) của mỗi đỉnh. Khi lần đầu tiên duyệt tới đỉnh u, chúng ta gán cho disc[u] một giá trị duy nhất tăng dần (sử dụng một bộ đếm thời gian toàn cục). disc[u] cho biết thứ tự duyệt đỉnh.
low (Lowest reachable time): Một mảng quan trọng ghi lại low[u]. Giá trị low[u] là giá trị disc nhỏ nhất có thể đạt được từ đỉnh u thông qua các đỉnh trong cây DFS con của u (bao gồm cả u), có thể sử dụng tối đa một cạnh ngược (back-edge) để "nhảy" ra khỏi cây con đó và đi tới một đỉnh đã được duyệt nhưng vẫn còn nằm trong ngăn xếp xử lý (on stack).
Stack: Một ngăn xếp (stack) chứa các đỉnh hiện đang nằm trong cây đệ quy DFS và có khả năng thuộc về cùng một SCC.
onStack: Một mảng boolean để đánh dấu xem một đỉnh có đang nằm trong ngăn xếp stack hay không. Điều này giúp phân biệt giữa các đỉnh đã thăm nhưng đã được gán vào một SCC nào đó (và không còn trong stack) với các đỉnh đã thăm nhưng vẫn đang trong quá trình tìm kiếm SCC (và còn trong stack).

Cách thuật toán hoạt động (qua DFS):

Chúng ta thực hiện một hàm DFS đệ quy, giả sử gọi là tarjanDFS(u) bắt đầu từ đỉnh u.

Khám phá đỉnh u:
- Khi lần đầu tiên thăm u, gán disc[u] = low[u] = timer. Tăng timer lên 1.
- Đẩy u vào ngăn xếp stack và đánh dấu onStack[u] = true.
Duyệt các đỉnh kề v của u:
- Đối với mỗi đỉnh kề v của u:
  - Nếu v chưa được thăm (disc[v] chưa được gán giá trị, thường khởi tạo là -1):
    - Đây là một cạnh cây (tree edge). Đệ quy gọi 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 có nghĩa là đỉnh u có thể đạt được bất kỳ đỉnh nào mà v có thể đạt được thông qua cây con của v.
  - Nếu v đã được thăm (disc[v] đã được gán giá trị) VÀ v đang nằm trong ngăn xếp (onStack[v] == true):
    - Đây là một cạnh ngược (back-edge) hoặc cạnh chéo (cross-edge) đi đến một đỉnh vẫn còn trong stack xử lý. Đỉnh v phải là một "tổ tiên" của u trong cây DFS hiện tại hoặc thuộc cùng một SCC đang được xây dựng.
    - Cập nhật low[u] = min(low[u], disc[v]). Lưu ý quan trọng: Chúng ta sử dụng disc[v] ở đây, không phải low[v]. Lý do là cạnh u -> v là một cạnh trực tiếp từ cây con của u tới v, và v đang ở trên stack, biểu thị v nằm trong cùng một chu trình hoặc SCC tiềm năng với u. disc[v] là thời điểm khám phá của v, là giá trị "cao" hơn trên cây DFS (trừ khi v là tổ tiên trực tiếp). Việc sử dụng disc[v] giúp low[u] phản ánh khả năng đi ngược lại tới một đỉnh đã thăm và vẫn còn liên quan (trên stack) thông qua cạnh u -> v. Nếu v đã thăm nhưng không còn trên stack (onStack[v] == false), cạnh u -> v là một cạnh chéo hoặc cạnh thuận tới một đỉnh đã thuộc về một SCC khác đã được xác định xong; chúng ta bỏ qua cạnh này vì nó không ảnh hưởng đến low[u] (nó chỉ dẫn đến một SCC đã hoàn thành).
  - Nếu v đã thăm nhưng không còn trên stack (onStack[v] == false):
    - Bỏ qua cạnh này. Đỉnh v đã thuộc về một SCC khác đã được xử lý xong.
Kiểm tra xem u có phải là gốc của một SCC hay không:
- Sau khi đã duyệt xong tất cả các đỉnh kề của u và xử lý các lời gọi đệ quy, kiểm tra điều kiện: if (low[u] == disc[u]).
- Nếu điều kiện này đúng, đỉnh u là gốc (root) của một Thành phần liên thông mạnh.
- Tất cả các đỉnh từ u trở lên trên ngăn xếp stack (cho đến đỉnh u được đưa ra khỏi stack) tạo thành một SCC.
- Chúng ta lần lượt lấy các đỉnh ra khỏi ngăn xếp, đánh dấu onStack của chúng là false, và đưa chúng vào cùng một SCC cho đến khi lấy ra được đỉnh u.

Lặp lại quá trình DFS này cho tất cả các đỉnh chưa được thăm ban đầu để đảm bảo tìm thấy tất cả SCC trong các thành phần liên thông yếu khác nhau của đồ thị.

Ví dụ Minh Họa (Theo dõi bước đi)

Xét đồ thị sau:

  A ---> B
  ^      |
  |      v
  C <--- D ---> E
  |      ^
  |      |
  F ---> G

Edges: A->B, B->C, C->A, C->D, D->E, E->D, F->G, G->D.

Vertices: A, B, C, D, E, F, G. Total V = 7.

Chúng ta sẽ theo dõi disc, low, và stack. Khởi tạo timer = 0, disc và low với -1, onStack là false.

Bắt đầu DFS từ A: tarjanDFS(A)
- disc[A] = 0, low[A] = 0, stack = [A], onStack[A] = true, timer = 1.
- Xem xét cạnh A->B: B chưa thăm. Gọi tarjanDFS(B).
  - disc[B] = 1, low[B] = 1, stack = [A, B], onStack[B] = true, timer = 2.
  - Xem xét cạnh B->C: C chưa thăm. Gọi tarjanDFS(C).
    - disc[C] = 2, low[C] = 2, stack = [A, B, C], onStack[C] = true, timer = 3.
    - Xem xét cạnh C->A: A đã thăm (disc[A]=0) và onStack[A]=true. Đây là back-edge. Cập nhật low[C] = min(low[C], disc[A]) = min(2, 0) = 0.
    - Xem xét cạnh C->D: D chưa thăm. Gọi tarjanDFS(D).
      - disc[D] = 3, low[D] = 3, stack = [A, B, C, D], onStack[D] = true, timer = 4.
      - Xem xét cạnh D->E: E chưa thăm. Gọi tarjanDFS(E).
        
        disc[E] = 4, low[E] = 4, stack = [A, B, C, D, E], onStack[E] = true, timer = 5.
        
        Xem xét cạnh E->D: D đã thăm (disc[D]=3) và onStack[D]=true. Back-edge. Cập nhật low[E] = min(low[E], disc[D]) = min(4, 3) = 3.
        
        E không còn đỉnh kề nào khác. Kiểm tra low[E] == disc[E] (3 == 4)? Không.
        
        Trở về D.
      - Sau khi gọi tarjanDFS(E) trả về, cập nhật low[D] = min(low[D], low[E]) = min(3, 3) = 3.
      - D không còn đỉnh kề nào khác chưa thăm. Kiểm tra low[D] == disc[D] (3 == 3)? Có! D là gốc của một SCC.
      - Bắt đầu pop stack cho đến khi gặp D:
        
        Pop E. SCC = {E}, onStack[E] = false. stack = [A, B, C, D].
        
        Pop D. SCC = {E, D}, onStack[D] = false. stack = [A, B, C].
      - SCC tìm thấy: {D, E}.
      - Trở về C.
    - Sau khi gọi tarjanDFS(D) trả về, cập nhật low[C] = min(low[C], low[D]) = min(0, 3) = 0.
    - C không còn đỉnh kề nào khác chưa thăm hoặc trên stack. Kiểm tra low[C] == disc[C] (0 == 2)? Có! C là gốc của một SCC.
    - Bắt đầu pop stack cho đến khi gặp C:
      - Pop C. SCC = {C}, onStack[C] = false. stack = [A, B].
      - Pop B. SCC = {C, B}, onStack[B] = false. stack = [A].
      - Pop A. SCC = {C, B, A}, onStack[A] = false. stack = [].
    - SCC tìm thấy: {A, B, C}.
    - Trở về B.
  - Sau khi gọi tarjanDFS(C) trả về, cập nhật low[B] = min(low[B], low[C]) = min(1, 0) = 0.
  - B không còn đỉnh kề nào khác. Kiểm tra low[B] == disc[B] (0 == 1)? Không.
  - Trở về A.
- Sau khi gọi tarjanDFS(B) trả về, cập nhật low[A] = min(low[A], low[B]) = min(0, 0) = 0.
- A không còn đỉnh kề nào khác. Kiểm tra low[A] == disc[A] (0 == 0)? Có! A là gốc của một SCC.
- Bắt đầu pop stack... Nhưng stack rỗng! Điều này xảy ra vì SCC {A, B, C} đã được xử lý khi pop C. Điều này minh chứng rằng các đỉnh trong SCC được pop ra cùng lúc khi gốc của chúng được xác định.
Quay lại hàm chính: Duyệt các đỉnh 0..V-1. A, B, C, D, E đã thăm. Tiếp tục với F.
- F chưa thăm (disc[F] là -1). Bắt đầu DFS từ F: tarjanDFS(F).
  - disc[F] = 5, low[F] = 5, stack = [F], onStack[F] = true, timer = 6.
  - Xem xét cạnh F->G: G chưa thăm. Gọi tarjanDFS(G).
    - disc[G] = 6, low[G] = 6, stack = [F, G], onStack[G] = true, timer = 7.
    - Xem xét cạnh G->D: D đã thăm (disc[D]=3) nhưng onStack[D]=false. Bỏ qua.
    - G không còn đỉnh kề khác. Kiểm tra low[G] == disc[G] (6 == 6)? Có! G là gốc của một SCC.
    - Pop G. SCC = {G}, onStack[G] = false. stack = [F].
    - SCC tìm thấy: {G}.
    - Trở về F.
  - Sau khi gọi tarjanDFS(G) trả về, cập nhật low[F] = min(low[F], low[G]) = min(5, 6) = 5.
  - F không còn đỉnh kề khác. Kiểm tra low[F] == disc[F] (5 == 5)? Có! F là gốc của một SCC.
  - Pop F. SCC = {F}, onStack[F] = false. stack = [].
  - SCC tìm thấy: {F}.
Kết thúc: Tất cả đỉnh đã được thăm. Các SCC đã tìm thấy là {A, B, C}, {D, E}, {F}, {G}. (Lưu ý thứ tự pop stack có thể làm cho các SCC in ra có thứ tự đỉnh khác nhau, nhưng tập hợp đỉnh là đúng).

Kết quả: Các SCC của đồ thị là {A, B, C}, {D, E}, {F}, {G}. Điều này khớp với phân tích ban đầu (trừ việc các đỉnh đơn độc không có cạnh đi ra/đi vào chính nó cũng là các SCC).

Triển khai Thuật toán Tarjan bằng C++

Bây giờ, hãy cùng viết mã C++ để thực hiện thuật toán mạnh mẽ này.

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

using namespace std;

const int MAXN = 10005; // Giả định số đỉnh tối đa

vector<vector<int>> adj; // Danh sách kề biểu diễn đồ thị có hướng
vector<int> disc, low; // Mảng discovery time và lowest reachable time
stack<int> st;          // Ngăn xếp lưu các đỉnh đang trong cây đệ quy DFS
vector<bool> onStack;   // Mảng kiểm tra đỉnh có đang trong stack không
int timer;              // Biến đếm thời gian cho discovery time
vector<vector<int>> sccs; // Vector lưu trữ các SCC tìm được

// Hàm DFS chính của thuật toán Tarjan
void tarjanDFS(int u) {
    // 1. Khám phá đỉnh u
    disc[u] = low[u] = timer++;
    st.push(u);
    onStack[u] = true;

    // 2. Duyệt các đỉnh kề v của u
    for (int v : adj[u]) {
        // Nếu v chưa thăm (disc[v] vẫn là -1)
        if (disc[v] == -1) {
            // Cạnh cây: đệ quy và cập nhật low[u] từ low[v]
            tarjanDFS(v);
            low[u] = min(low[u], low[v]);
        }
        // Nếu v đã thăm VÀ v đang ở trong stack
        else if (onStack[v]) {
            // Cạnh ngược hoặc cạnh chéo tới đỉnh trên stack: cập nhật low[u] từ disc[v]
            low[u] = min(low[u], disc[v]);
        }
        // Nếu v đã thăm nhưng không ở trong stack -> bỏ qua (thuộc SCC khác đã hoàn thành)
    }

    // 3. Kiểm tra xem u có phải là gốc của một SCC hay không
    if (low[u] == disc[u]) {
        vector<int> current_scc;
        // Pop các đỉnh từ stack cho đến khi gặp u
        while (true) {
            int v = st.top();
            st.pop();
            onStack[v] = false; // Đỉnh đã thuộc SCC, không còn trong stack xử lý
            current_scc.push_back(v);

            if (v == u) {
                break;
            }
        }
        sccs.push_back(current_scc); // Lưu trữ SCC vừa tìm được
    }
}

// Hàm chính để tìm tất cả SCC trong đồ thị
void findSCCs(int n) {
    // Khởi tạo các mảng và biến
    disc.assign(n + 1, -1); // Khởi tạo disc với -1 (chưa thăm)
    low.assign(n + 1, -1);  // Khởi tạo low với -1
    onStack.assign(n + 1, false);
    while (!st.empty()) st.pop(); // Xóa stack cũ nếu có
    timer = 0;
    sccs.clear(); // Xóa danh sách SCC cũ nếu có

    // Đảm bảo duyệt qua tất cả các đỉnh để xử lý các thành phần liên thông yếu khác nhau
    for (int i = 1; i <= n; ++i) { // Giả sử đỉnh từ 1 đến n
        if (disc[i] == -1) { // Nếu đỉnh i chưa thăm
            tarjanDFS(i);
        }
    }
}

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

    cout << "Nhap so dinh va so canh: ";
    cin >> n >> m;

    adj.assign(n + 1, vector<int>()); // Khởi tạo danh sách kề cho n+1 đỉnh (sử dụng đỉnh từ 1 đến n)

    cout << "Nhap cac canh (u v):" << endl;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // Thêm cạnh từ u đến v
    }

    findSCCs(n); // Gọi hàm tìm SCC

    cout << "\nCac thanh phan lien thong manh (SCCs) la:" << endl;
    for (const auto& scc : sccs) {
        cout << "{ ";
        for (int i = 0; i < scc.size(); ++i) {
            cout << scc[i] << (i == scc.size() - 1 ? "" : ", ");
        }
        cout << " }" << endl;
    }

    return 0;
}

Giải thích Code C++:

Includes and Constants:
- #include <iostream>, <vector>, <stack>, <algorithm>: Các thư viện cần thiết cho input/output, sử dụng vector, stack và hàm min.
- MAXN: Hằng số định nghĩa kích thước tối đa của đồ thị (có thể thay đổi tùy bài toán).
Global Variables:
- adj: vector<vector<int>> biểu diễn danh sách kề của đồ thị có hướng. adj[u] là vector chứa các đỉnh v mà có cạnh u -> v.
- disc, low: vector<int> lưu trữ thời điểm khám phá và giá trị low cho mỗi đỉnh. Kích thước n+1 nếu đỉnh đánh số từ 1. Khởi tạo bằng -1 để đánh dấu chưa thăm.
- st: stack<int> để lưu trữ các đỉnh trong đường đi DFS hiện tại có khả năng thuộc cùng một SCC.
- onStack: vector<bool> đánh dấu đỉnh có đang ở trong st không.
- timer: Biến đếm global, tăng sau mỗi lần gán disc.
- sccs: vector<vector<int>> để lưu trữ kết quả, mỗi vector con là một SCC.
tarjanDFS(int u) Function:
- Đây là hàm DFS đệ quy cốt lõi.
- disc[u] = low[u] = timer++;: Gán thời điểm khám phá và khởi tạo low cho đỉnh u. Đẩy u vào stack và đánh dấu onStack[u] = true.
- Vòng lặp for (int v : adj[u]): Duyệt qua tất cả các đỉnh kề v của u.
  - if (disc[v] == -1): Nếu v chưa thăm (cạnh cây), đệ quy tarjanDFS(v). Sau đó, cập nhật low[u] = min(low[u], low[v]).
  - else if (onStack[v]): Nếu v đã thăm và đang ở trên stack (cạnh ngược hoặc chéo tới đỉnh trên stack), cập nhật low[u] = min(low[u], disc[v]).
- if (low[u] == disc[u]): Đây là điều kiện để xác định gốc của một SCC.
  - Một vòng lặp while pop các đỉnh từ stack. Các đỉnh này chính là các thành viên của SCC mà u là gốc.
  - Đỉnh được pop ra được thêm vào current_scc và onStack của nó được đặt thành false.
  - Vòng lặp dừng khi đỉnh u được pop ra.
  - current_scc được thêm vào danh sách sccs.
findSCCs(int n) Function:
- Hàm này chuẩn bị cho quá trình tìm kiếm.
- Nó khởi tạo tất cả các mảng và biến cần thiết (đặt disc, low về -1, onStack về false, reset timer, xóa stack và danh sách sccs).
- Vòng lặp for (int i = 1; i <= n; ++i): Duyệt qua tất cả các đỉnh từ 1 đến n. Nếu một đỉnh chưa được thăm (disc[i] == -1), điều đó có nghĩa là nó thuộc về một thành phần liên thông yếu chưa được khám phá, và chúng ta bắt đầu một cuộc duyệt DFS mới từ đỉnh đó bằng cách gọi tarjanDFS(i).
main() Function:
- Nhập số đỉnh n và số cạnh m.
- Khởi tạo danh sách kề adj.
- Nhập các cạnh và xây dựng danh sách kề.
- Gọi findSCCs(n) để thực hiện thuật toán.
- In ra các SCC đã tìm được từ vector sccs.

Độ phức tạp của Thuật toán Tarjan

Độ phức tạp thời gian: O(V + E), trong đó V là số đỉnh và E là số cạnh. Mỗi đỉnh và mỗi cạnh chỉ được thăm một lần trong quá trình DFS. Các thao tác trên stack mất thời gian O(1) trung bình cho mỗi đỉnh.
Độ phức tạp không gian: O(V + E). Chúng ta cần không gian cho danh sách kề (O(V+E)), các mảng disc, low, onStack (O(V)) và ngăn xếp stack (trong trường hợp xấu nhất có thể chứa tất cả các đỉnh, O(V)).

Đây là một độ phức tạp rất hiệu quả, tuyến tính theo kích thước đồ thị.

Bài tập ví dụ:

Điều tra chuyến bay

Để chuẩn bị cho buổi trình diễn thời trang, FullHouse Dev được giao nhiệm vụ lập kế hoạch di chuyển cho các người mẫu từ thành phố Syrjälä đến Lehmälä bằng máy bay. Với kinh nghiệm trong việc tối ưu hóa, họ cần tìm ra câu trả lời cho các câu hỏi sau:

chi phí tối thiểu cho một hành trình?
có bao nhiêu hành trình có chi phí tối thiểu? (theo modulo $10^9+7$)
số chuyến bay ít nhất trong một hành trình có chi phí tối thiểu?
số chuyến bay nhiều nhất trong một hành trình có chi phí tối thiểu?

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 chuyến bay. Các thành phố được đánh số từ $1,2,\ldots,n$. Thành phố 1 là Syrjälä, và thành phố $n$ là Lehmälä.
$m$ dòng tiếp theo mô tả các chuyến bay. Mỗi dòng có ba số nguyên $a$, $b$, và $c$: có một chuyến bay từ thành phố $a$ đến thành phố $b$ với giá $c$. Tất cả các chuyến bay đều một chiều.
Luôn tồn tại ít nhất một hành trình từ Syrjälä đến Lehmälä.

OUTPUT FORMAT:

In ra bốn số nguyên theo thứ tự yêu cầu trong đề bài.

Ràng buộc:

$1 \leq n \leq 10^5$
$1 \leq m \leq 2 \cdot 10^5$
$1 \leq a,b \leq n$
$1 \leq c \leq 10^9$

Ví dụ

INPUT

OUTPUT

5 2 1 2

Giải thích

Chi phí tối thiểu là 5 (có thể đi trực tiếp từ 1 đến 4)
Có 2 hành trình với chi phí tối thiểu: 1→4 và 1→2→4
Số chuyến bay ít nhất trong hành trình chi phí tối thiểu là 1 (đi trực tiếp 1→4)
Số chuyến bay nhiều nhất trong hành trình chi phí tối thiểu là 2 (đi 1→2→4) Chào bạn, đây là hướng dẫn giải bài toán "Điều tra chuyến bay" sử dụng C++:

Bài toán yêu cầu tìm 4 thông tin về các hành trình từ thành phố 1 đến thành phố n trên một đồ thị có hướng, có trọng số (chi phí), trong đó chúng ta chỉ quan tâm đến các hành trình có chi phí tối thiểu.

Nhận dạng bài toán: Đây là bài toán tìm đường đi ngắn nhất (shortest path) trên đồ thị có hướng với trọng số không âm. Trọng số ở đây là chi phí chuyến bay. Ngoài việc tìm chi phí ngắn nhất, chúng ta còn cần đếm số lượng đường đi ngắn nhất và tìm độ dài (số cạnh/chuyến bay) min/max của những đường đi ngắn nhất đó.
Thuật toán cơ bản: Với trọng số không âm, thuật toán Dijkstra là lựa chọn phù hợp và hiệu quả nhất để tìm đường đi ngắn nhất từ một đỉnh nguồn (thành phố 1) đến tất cả các đỉnh khác.
Mở rộng thuật toán Dijkstra: Để trả lời các câu hỏi bổ sung, chúng ta cần mở rộng thuật toán Dijkstra. Thay vì chỉ lưu chi phí tối thiểu dist[u] từ nguồn đến đỉnh u, chúng ta sẽ lưu thêm các thông tin sau cho mỗi đỉnh u:
- dist[u]: Chi phí tối thiểu từ nguồn đến u.
- count[u]: Số lượng hành trình có chi phí tối thiểu từ nguồn đến u.
- min_flights[u]: Số chuyến bay ít nhất trong một hành trình có chi phí tối thiểu từ nguồn đến u.
- max_flights[u]: Số chuyến bay nhiều nhất trong một hành trình có chi phí tối thiểu từ nguồn đến u.
Cập nhật thông tin trong quá trình Dijkstra: Khi thuật toán Dijkstra xem xét mở rộng từ một đỉnh u đến đỉnh kề v qua một cạnh có trọng số w:
- Trường hợp 1: Tìm thấy đường đi TỐT HƠN đến v qua u (dist[u] + w < dist[v])
  - Cập nhật dist[v] = dist[u] + w.
  - Số cách đến v với chi phí mới này chỉ là số cách đến u: count[v] = count[u].
  - Số chuyến bay min/max đến v là số chuyến bay min/max đến u cộng thêm 1 chuyến từ u đến v: min_flights[v] = min_flights[u] + 1, max_flights[v] = max_flights[u] + 1.
  - Đẩy (dist[v], v) vào hàng đợi ưu tiên.
- Trường hợp 2: Tìm thấy đường đi CÓ CÙNG CHI PHÍ TỐI THIỂU đến v qua u (dist[u] + w == dist[v])
  - Đây là một đường đi tối thiểu mới đến v. Cộng số cách đến u vào tổng số cách đến v: count[v] = (count[v] + count[u]) % MOD. (Nhớ lấy modulo).
  - Cập nhật số chuyến bay min/max bằng cách so sánh với đường đi mới này: min_flights[v] = min(min_flights[v], min_flights[u] + 1), max_flights[v] = max(max_flights[v], max_flights[u] + 1).
  - Lưu ý: Trong một số cài đặt Dijkstra, khi tìm thấy đường đi cùng chi phí, đỉnh v có thể đã được xử lý hoặc đang trong hàng đợi. Để đảm bảo cập nhật đúng, khi dist[u] + w == dist[v], bạn vẫn nên xử lý việc cập nhật count, min_flights, max_flights cho v. Nếu sử dụng hàng đợi ưu tiên thông thường (không hỗ trợ giảm khóa), việc đẩy lại v vào hàng đợi có thể cần thiết nếu min_flights hoặc max_flights thay đổi, hoặc đơn giản là xử lý các entry cũ trong hàng đợi khi rút ra (kiểm tra c > dist[u]). Cách phổ biến là đẩy lại vào hàng đợi nếu các thông tin phụ (count, min/max flights) cần được kết hợp/cập nhật.
Khởi tạo:
- dist[1] = 0, dist[u] = INF (vô cùng lớn) cho u \neq 1.
- count[1] = 1, count[u] = 0 cho u \neq 1.
- min_flights[1] = 0, min_flights[u] = INF cho u \neq 1.
- max_flights[1] = 0, max_flights[u] = -INF (vô cùng nhỏ) cho `u \neq 1$. (Hoặc dùng giá trị đủ lớn/nhỏ để so sánh min/max).
Triển khai:
- Sử dụng cấu trúc dữ liệu đồ thị phù hợp, ví dụ danh sách kề (vector<pair<int, int>> adj[N]).
- Sử dụng hàng đợi ưu tiên (priority_queue) để lưu trữ các cặp (cost, node) theo thứ tự chi phí tăng dần.
- Sử dụng kiểu dữ liệu long long cho dist để chứa chi phí lớn.
- Sử dụng modulo 10^9 + 7 khi cập nhật count.
- Hằng số cho vô cùng (INF) cần đủ lớn.
Kết quả: Sau khi thuật toán Dijkstra kết thúc, các giá trị cần tìm sẽ là dist[n], count[n], min_flights[n], và max_flights[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.