Bài 19.1. BFS 0-K và ứng dụng trong tìm đường

Trong thế giới rộng lớn của Cấu trúc dữ liệu và Giải thuật, bài toán tìm đường đi ngắn nhất luôn chiếm một vị trí quan trọng. Chúng ta đã quen thuộc với Breadth-First Search (BFS) cho đồ thị không trọng số (hay trọng số 1), và Dijkstra cho đồ thị có trọng số không âm bất kỳ. Nhưng điều gì sẽ xảy ra khi đồ thị của chúng ta có một cấu trúc trọng số đặc biệt: chỉ gồm các cạnh có trọng số là 0 hoặc 1?

Liệu chúng ta có thể tối ưu hơn việc sử dụng Dijkstra thông thường với hàng đợi ưu tiên? Câu trả lời là có, và kỹ thuật đó chính là BFS 0-K (hay còn gọi là BFS 0-1). Đây là một biến thể mạnh mẽ của BFS, được thiết kế riêng để giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị đặc biệt này một cách cực kỳ hiệu quả.

Tại sao lại cần BFS 0-K?

Hãy phân tích một chút.

BFS thông thường: Hoạt động dựa trên nguyên tắc duyệt từng "lớp" một. Nó đảm bảo tìm thấy đường đi ngắn nhất trên đồ thị không trọng số vì mọi bước di chuyển đều tốn chi phí như nhau (bằng 1). Khi gặp cạnh trọng số 0, BFS thông thường sẽ xử lý nó giống như cạnh trọng số 1, dẫn đến kết quả sai lầm về tổng chi phí đường đi.
Dijkstra: Sử dụng hàng đợi ưu tiên để luôn mở rộng đường đi từ đỉnh có khoảng cách nhỏ nhất hiện tại. Điều này đúng đắn cho mọi trọng số không âm. Tuy nhiên, thao tác trên hàng đợi ưu tiên (như push và pop) có độ phức tạp logarit (O(log V) hoặc O(log E), tùy cài đặt hàng đợi). Trên đồ thị lớn, chi phí này có thể đáng kể.

Xét trường hợp trọng số chỉ là 0 hoặc 1:

Một cạnh có trọng số 1 giống như một bước di chuyển bình thường trong BFS, làm tăng tổng chi phí lên 1 đơn vị.
Một cạnh có trọng số 0 lại đặc biệt. Nó cho phép ta "nhảy" tới đỉnh kế tiếp mà không tốn thêm chi phí. Điều này có nghĩa là đỉnh vừa đến (qua cạnh 0) đang ở cùng "lớp chi phí" với đỉnh hiện tại.

Chúng ta cần một cơ chế xử lý các cạnh trọng số 0 ngay lập tức hoặc ưu tiên hơn so với các cạnh trọng số 1. Điều này nghe có vẻ giống hàng đợi ưu tiên, nhưng vì chỉ có 2 mức ưu tiên (0 và 1), chúng ta có thể làm tốt hơn.

Cơ chế hoạt động của BFS 0-K: Sử dụng Deque

Điểm mấu chốt của BFS 0-K nằm ở việc sử dụng một deque (double-ended queue - hàng đợi hai đầu) thay vì hàng đợi thông thường.

Khi duyệt từ đỉnh u và gặp cạnh (u, v):
- Nếu cạnh có trọng số 0: Ta thêm đỉnh v vào phía trước (front) của deque. Điều này đảm bảo đỉnh v sẽ được xử lý trước những đỉnh đã được thêm vào phía sau. Nó duy trì ý tưởng rằng v đang ở cùng mức chi phí với u.
- Nếu cạnh có trọng số 1: Ta thêm đỉnh v vào phía sau (back) của deque. Điều này đảm bảo đỉnh v sẽ được xử lý sau những đỉnh được thêm vào phía trước (tức là những đỉnh đạt được với chi phí 0), đẩy v sang "lớp chi phí" tiếp theo.

Bằng cách này, deque luôn ưu tiên xử lý các đỉnh có thể đạt được với chi phí thấp nhất hiện tại (thông qua các cạnh 0), trước khi chuyển sang các đỉnh ở mức chi phí cao hơn (đạt được thông qua cạnh 1).

Các bước thực hiện chi tiết:

Khởi tạo mảng dist (khoảng cách ngắn nhất) cho tất cả các đỉnh bằng vô cùng (infinity), trừ đỉnh nguồn s có dist[s] = 0.
Tạo một deque và thêm đỉnh nguồn s vào phía trước của deque.
Trong khi deque chưa rỗng:
- Lấy đỉnh u ở phía trước của deque và loại bỏ nó.
- Duyệt qua tất cả các đỉnh kề v của u với trọng số cạnh w (là 0 hoặc 1).
- Nếu dist[u] + w < dist[v]: (Đây là bước "thư giãn" - relaxation, tương tự Dijkstra)
  - Cập nhật dist[v] = dist[u] + w.
  - Nếu w == 0: Thêm v vào phía trước của deque.
  - Nếu w == 1: Thêm v vào phía sau của deque.

Độ phức tạp: Mỗi đỉnh và mỗi cạnh được xử lý một số lần cố định (đỉnh bị pop ra khỏi deque tối đa 1 lần, cạnh được duyệt khi đỉnh nguồn của nó bị pop). Thao tác thêm/bớt ở cả hai đầu deque mất thời gian O(1). Do đó, độ phức tạp tổng thể là O(V + E), tương tự như BFS thông thường và tốt hơn Dijkstra O((V+E) log V) trên các đồ thị lớn.

So sánh với BFS và Dijkstra

BFS vs. BFS 0-K: BFS 0-K là tổng quát hóa của BFS. Nếu tất cả trọng số cạnh đều là 1, BFS 0-K với deque sẽ hoạt động giống hệt BFS thông thường (vì tất cả sẽ được thêm vào phía sau).
Dijkstra vs. BFS 0-K: BFS 0-K là một trường hợp đặc biệt được tối ưu của Dijkstra khi trọng số chỉ có 0 và 1. Nó đạt được hiệu quả O(V+E) nhờ việc thay thế hàng đợi ưu tiên bằng deque.

BFS 0-K là lựa chọn tối ưu khi bạn đối mặt với bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số chỉ 0 hoặc 1.

Ví dụ Minh Họa 1: Đồ thị Trừu Tượng

Xét một đồ thị có hướng với các đỉnh A, B, C, D, E và các cạnh cùng trọng số như sau:

A -> B (trọng số 0)
A -> C (trọng số 1)
B -> D (trọng số 1)
C -> D (trọng số 0)
C -> E (trọng số 1)
D -> E (trọng số 0)

Chúng ta muốn tìm đường đi ngắn nhất từ A đến E.

Minh họa các bước sử dụng BFS 0-K:

dist = {A: 0, B: inf, C: inf, D: inf, E: inf}. Deque: [A]
Pop A (dist 0).
- A -> B (w=0): dist[B] = dist[A] + 0 = 0. Push B front. Deque: [B]
- A -> C (w=1): dist[C] = dist[A] + 1 = 1. Push C back. Deque: [B, C]
Pop B (dist 0).
- B -> D (w=1): dist[D] = dist[B] + 1 = 1. Push D back. Deque: [C, D]
Pop C (dist 1).
- C -> D (w=0): dist[C] + 0 = 1 + 0 = 1. Current dist[D] is 1. No update (1 < 1 is false).
- C -> E (w=1): dist[C] + 1 = 1 + 1 = 2. dist[E] = 2. Push E back. Deque: [D, E]
Pop D (dist 1).
- D -> E (w=0): dist[D] + 0 = 1 + 0 = 1. Current dist[E] is 2. Update dist[E] = 1. Push E front. Deque: [E, E] (Lưu ý: Đỉnh E có thể xuất hiện nhiều lần trong deque, nhưng chúng ta chỉ xử lý khi tìm thấy đường ngắn hơn).
Pop E (dist 1). Đến đích. Dist[E] = 1.
Pop E (dist 2 - the old one). current dist[E] is 1, 2 is not < 1, skip processing neighbors from this outdated entry.
Deque rỗng. Kết thúc.

Đường đi ngắn nhất từ A đến E có chi phí là 1. (Ví dụ: A -> B (0) -> D (1) -> E (0). Tổng chi phí 0 + 1 + 0 = 1).

Mã C++ Minh Họa cho Đồ thị Trừu Tượng

#include <iostream>
#include <vector>
#include <deque>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// Cấu trúc lưu cạnh: đỉnh đích và trọng số (0 hoặc 1)
struct Edge {
    int to;
    int weight;
};

int main() {
    int num_vertices = 5; // A, B, C, D, E
    // Sử dụng danh sách kề: adj[i] là vector các cạnh xuất phát từ đỉnh i
    // Ánh xạ: A=0, B=1, C=2, D=3, E=4
    vector<vector<Edge>> adj(num_vertices);

    // Thêm các cạnh
    adj[0].push_back({1, 0}); // A -> B (0)
    adj[0].push_back({2, 1}); // A -> C (1)
    adj[1].push_back({3, 1}); // B -> D (1)
    adj[2].push_back({3, 0}); // C -> D (0)
    adj[2].push_back({4, 1}); // C -> E (1)
    adj[3].push_back({4, 0}); // D -> E (0)

    int start_node = 0; // A
    int end_node = 4;   // E

    vector<int> dist(num_vertices, INF);
    deque<int> dq;

    dist[start_node] = 0;
    dq.push_front(start_node);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        // Quan trọng: Kiểm tra xem đỉnh này đã được xử lý với khoảng cách tốt hơn chưa
        // Điều này có thể xảy ra vì một đỉnh có thể được thêm vào deque nhiều lần.
        // Tuy nhiên, với 0-1 BFS, đỉnh sẽ chỉ được pop ra khi khoảng cách của nó
        // là nhỏ nhất trong deque, và lần pop đầu tiên là lần tìm thấy đường đi
        // ngắn nhất. Lần pop sau chỉ xảy ra nếu nó được thêm vào lại do tìm thấy
        // đường đi NGẮN HƠN nữa, điều này không xảy ra trong 0-1 BFS vì dist
        // chỉ tăng hoặc giữ nguyên. Nhưng việc kiểm tra này vẫn an toàn
        // và cần thiết trong các biến thể khác hoặc để đảm bảo logic.
        // Với 0-1 BFS, dist[u] khi pop ra là dist ngắn nhất đến u.
        // Nên chỉ cần duyệt cạnh kề.

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (weight == 0) {
                    dq.push_front(v); // Ưu tiên đỉnh đạt được bằng cạnh 0
                } else { // weight == 1
                    dq.push_back(v); // Đỉnh đạt được bằng cạnh 1 xử lý sau
                }
            }
        }
    }

    cout << "Khoang cach ngan nhat tu " << start_node << " den " << end_node << " la: ";
    if (dist[end_node] == INF) {
        cout << "Khong co duong di" << endl;
    } else {
        cout << dist[end_node] << endl;
    }

    return 0;
}

Giải thích code:

Edge struct: Đơn giản lưu thông tin về đỉnh đích và trọng số của cạnh.
adj: vector<vector<Edge>> là cách biểu diễn đồ thị bằng danh sách kề. Mỗi phần tử adj[i] là một vector chứa tất cả các cạnh đi ra từ đỉnh i.
dist: vector<int> lưu khoảng cách ngắn nhất tìm được từ đỉnh nguồn đến mỗi đỉnh khác. Khởi tạo bằng INF.
deque<int> dq: Hàng đợi hai đầu là trái tim của thuật toán.
Khởi tạo: dist[start_node] = 0 và thêm start_node vào dq.push_front().
Vòng while (!dq.empty()): Lặp cho đến khi không còn đỉnh nào trong deque.
int u = dq.front(); dq.pop_front();: Lấy đỉnh ở đầu deque (đỉnh có chi phí thấp nhất được ưu tiên) và loại bỏ nó.
Vòng for (const auto& edge : adj[u]): Duyệt qua tất cả các cạnh đi ra từ u.
if (dist[u] + weight < dist[v]): Kiểm tra xem có thể tìm thấy đường đi ngắn hơn đến v thông qua u hay không.
dist[v] = dist[u] + weight;: Nếu có, cập nhật khoảng cách ngắn nhất đến v.
if (weight == 0) dq.push_front(v); else dq.push_back(v);: Đây là logic chính của BFS 0-K. Đỉnh v được thêm vào trước nếu cạnh có trọng số 0, hoặc thêm vào sau nếu trọng số 1.
Cuối cùng, in ra khoảng cách ngắn nhất đến end_node.

Ví dụ Minh Họa 2: Bài Toán Lưới (Grid)

BFS 0-K rất phổ biến trong các bài toán trên lưới (grid) khi một số loại di chuyển "đặc biệt" tốn ít chi phí hơn (hoặc bằng 0) so với di chuyển thông thường.

Xét bài toán: Tìm đường đi ngắn nhất (theo số bước di chuyển) từ một ô bắt đầu S đến ô kết thúc E trên một lưới kích thước R x C. Các ô có thể là:

.: Ô trống, có thể đi qua. Chi phí di chuyển vào ô này là 1.
#: Ô vật cản, không thể đi qua.
*: Ô đặc biệt, có thể đi qua, nhưng chi phí di chuyển vào ô này chỉ là 0.

Chúng ta muốn tìm đường đi với tổng chi phí nhỏ nhất.

Bài toán này có thể mô hình hóa thành đồ thị:

Đỉnh: Mỗi ô (r, c) trên lưới là một đỉnh của đồ thị.
Cạnh: Có cạnh từ ô (r1, c1) đến ô kề (r2, c2) (lên, xuống, trái, phải) nếu ô (r2, c2) không phải là vật cản (#).
Trọng số cạnh:
- Nếu ô đích (r2, c2) là ô trống (.), trọng số cạnh là 1.
- Nếu ô đích (r2, c2) là ô đặc biệt (*), trọng số cạnh là 0.

Đây chính xác là bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số chỉ 0 và 1, hoàn hảo cho BFS 0-K!

Mã C++ Minh Họa cho Bài Toán Lưới

#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

int main() {
    int R, C;
    cout << "Nhap so hang R: ";
    cin >> R;
    cout << "Nhap so cot C: ";
    cin >> C;

    vector<string> grid(R);
    cout << "Nhap luoi (" << R << "x" << C << ", '.' trong, '*' dac biet, '#' vat can, 'S' bat dau, 'E' ket thuc):" << endl;
    pair<int, int> start_pos, end_pos;
    for (int i = 0; i < R; ++i) {
        cin >> grid[i];
        for (int j = 0; j < C; ++j) {
            if (grid[i][j] == 'S') {
                start_pos = {i, j};
                grid[i][j] = '.'; // Xem S như ô trống sau khi xác định vị trí
            } else if (grid[i][j] == 'E') {
                end_pos = {i, j};
                grid[i][j] = '.'; // Xem E như ô trống sau khi xác định vị trí
            }
        }
    }

    // Khoảng cách: dist[r][c] là khoảng cách ngắn nhất đến ô (r, c)
    vector<vector<int>> dist(R, vector<int>(C, INF));
    deque<pair<int, int>> dq;

    dist[start_pos.first][start_pos.second] = 0;
    dq.push_front(start_pos);

    // Hướng di chuyển: len, xuong, trai, phai
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!dq.empty()) {
        pair<int, int> curr = dq.front();
        dq.pop_front();
        int r = curr.first;
        int c = curr.second;

        // Nếu đã đến đích, có thể dừng lại (tối ưu nhỏ)
        // if (r == end_pos.first && c == end_pos.second) {
        //     break;
        // }

        for (int i = 0; i < 4; ++i) { // Duyệt 4 hướng
            int nr = r + dr[i];
            int nc = c + dc[i];

            // Kiểm tra ô kế tiếp có hợp lệ không
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != '#') {
                int weight = (grid[nr][nc] == '*') ? 0 : 1; // Trọng số dựa vào loại ô

                if (dist[r][c] + weight < dist[nr][nc]) {
                    dist[nr][nc] = dist[r][c] + weight;
                    if (weight == 0) {
                        dq.push_front({nr, nc}); // Ô đặc biệt -> chi phí 0 -> ưu tiên
                    } else { // weight == 1
                        dq.push_back({nr, nc}); // Ô trống -> chi phí 1 -> xử lý sau
                    }
                }
            }
        }
    }

    cout << "Khoang cach ngan nhat tu S den E la: ";
    if (dist[end_pos.first][end_pos.second] == INF) {
        cout << "Khong co duong di" << endl;
    } else {
        cout << dist[end_pos.first][end_pos.second] << endl;
    }

    return 0;
}

Giải thích code:

Đọc kích thước lưới R, C và nội dung lưới. Xác định vị trí bắt đầu S và kết thúc E. Thay thế S và E bằng . để đơn giản hóa logic tính trọng số.
dist: vector<vector<int>> 2D lưu khoảng cách ngắn nhất đến mỗi ô (r, c).
deque<pair<int, int>> dq: Deque lưu các ô (r, c) cần thăm.
Khởi tạo: Khoảng cách đến ô bắt đầu là 0, các ô khác là INF. Thêm ô bắt đầu vào dq.push_front().
dr[], dc[]: Mảng giúp duyệt 4 ô kề một cách dễ dàng.
Vòng while (!dq.empty()): Lặp khi deque còn phần tử.
pair<int, int> curr = dq.front(); dq.pop_front();: Lấy ô ở đầu deque.
Vòng for (int i = 0; i < 4; ++i): Duyệt 4 hướng di chuyển.
Kiểm tra biên và vật cản (#).
Xác định weight: Nếu ô kế tiếp là *, weight là 0; ngược lại (là .), weight là 1.
if (dist[r][c] + weight < dist[nr][nc]): So sánh đường đi mới tìm được qua (r, c) có ngắn hơn đường đi tốt nhất đến (nr, nc) hiện tại không.
dist[nr][nc] = dist[r][c] + weight;: Cập nhật khoảng cách.
if (weight == 0) dq.push_front({nr, nc}); else dq.push_back({nr, nc});: Logic thêm vào deque dựa trên trọng số cạnh (loại ô).
Kết quả là dist tại vị trí ô kết thúc.

Bài tập ví dụ:

Đường bay dài nhất

Trong một ngày đẹp trời, FullHouse Dev đang tham quan một cánh đồng rộng lớn thì nhận được một bài toán thú vị. Họ được yêu cầu tìm đường bay dài nhất giữa hai thành phố, đi qua càng nhiều điểm dừng càng tốt.

Bài toán

FullHouse Dev cần tìm đường bay từ Syrjälä đến Lehmälä sao cho đi qua được nhiều thành phố nhất có thể. Họ được cung cấp danh sách các chuyến bay khả dụng và biết rằng không có chu trình có hướng nào trong mạng lưới bay này.

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$ đến $n$. Thành phố $1$ là Syrjälä, và thành phố $n$ là Lehmälä.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$: thể hiện một chuyến bay một chiều từ thành phố $a$ đến thành phố $b$.

OUTPUT FORMAT:

Dòng đầu tiên in ra số lượng thành phố tối đa có thể đi qua.
Dòng thứ hai in ra các thành phố theo thứ tự sẽ đi qua.
Nếu không có đường đi khả thi, in ra "IMPOSSIBLE".

Ràng buộc:

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

Ví dụ

INPUT

OUTPUT

4
1 3 4 5

Giải thích

Trong ví dụ này, đường đi tối ưu là đi từ thành phố 1 (Syrjälä) → 3 → 4 → 5 (Lehmälä), đi qua tổng cộng 4 thành phố. Mặc dù có thể đi theo đường 1 → 2 → 5, nhưng đường đi này chỉ đi qua 3 thành phố, không phải là tối ưu. Chào bạn, đây là hướng dẫn giải bài toán "Đường bay dài nhất" sử dụng C++.

Bài toán yêu cầu tìm đường đi từ thành phố 1 đến thành phố $n$ đi qua số lượng thành phố nhiều nhất trong một Đồ thị có hướng không chu trình (DAG). Đây là một bài toán tìm đường đi dài nhất trong DAG, có thể giải hiệu quả bằng Quy hoạch động (Dynamic Programming) kết hợp với Sắp xếp tô-pô (Topological Sort).

Ý tưởng chính:

Nhận diện bài toán: Đây là bài toán tìm đường đi dài nhất về số lượng đỉnh trong một Đồ thị có hướng không chu trình (DAG). DAGs cho phép giải bài toán đường đi dài nhất một cách hiệu quả, không như đồ thị tổng quát (có chu trình).
Quy hoạch động (DP):
- Định nghĩa trạng thái DP: Gọi dp[u] là số lượng thành phố tối đa trên đường đi từ thành phố 1 đến thành phố $u$.
- Mục tiêu: Tìm dp[n].
- Công thức chuyển trạng thái: Để đạt được đường đi dài nhất đến thành phố $v$, ta xét tất cả các thành phố $u$ có chuyến bay trực tiếp đến $v$ (tức là có cạnh $(u, v)$). Nếu ta đã tìm được đường đi dài nhất đến $u$ (tức dp[u] đã được tính), thì ta có thể kéo dài đường đi đó đến $v$. Số lượng thành phố trên đường đi qua $u$ đến $v$ sẽ là dp[u] + 1. Ta chọn đường đi nào cho kết quả lớn nhất: dp[v] = max(dp[v], dp[u] + 1) cho tất cả các $u$ có cạnh $(u, v)$.
- Trường hợp cơ sở: dp[1] = 1 (đường đi đến thành phố 1 chỉ có 1 thành phố là chính nó). Các dp[u] khác ban đầu được khởi tạo là 0 (hoặc một giá trị âm để biểu thị không thể đến được từ 1).
Thứ tự tính toán: Để tính dp[v] dựa trên dp[u], ta phải đảm bảo dp[u] đã được tính trước. Thứ tự này chính là thứ tự tô-pô của đồ thị. Sắp xếp tô-pô cho ta một thứ tự tuyến tính các đỉnh sao cho với mọi cạnh $(u, v)$, $u$ luôn xuất hiện trước $v$ trong thứ tự.
Kết hợp DP và Sắp xếp tô-pô: Ta có thể sử dụng thuật toán sắp xếp tô-pô (ví dụ: dùng hàng đợi và đếm "độ vào" - in-degree của các đỉnh) để xử lý các đỉnh theo đúng thứ tự. Khi xử lý một đỉnh $u$ trong quá trình sắp xếp tô-pô:
- Nếu dp[u] > 0 (nghĩa là $u$ có thể đến được từ 1), ta xét tất cả các đỉnh $v$ mà có cạnh từ $u$ đến $v$.
- Nếu dp[u] + 1 lớn hơn dp[v] hiện tại, cập nhật dp[v] = dp[u] + 1.
- Để truy vết đường đi, ta cần lưu lại đỉnh $u$ nào đã cho kết quả dp[v] tốt nhất khi cập nhật: parent[v] = u.
- Giảm độ vào của đỉnh $v$. Nếu độ vào của $v$ trở thành 0, thêm $v$ vào hàng đợi xử lý tiếp.
Kiểm tra kết quả: Sau khi xử lý xong tất cả các đỉnh theo thứ tự tô-pô (hoặc cho đến khi hàng đợi rỗng), giá trị dp[n] sẽ là số lượng thành phố tối đa. Nếu dp[n] vẫn là 0 (hoặc giá trị khởi tạo âm), nghĩa là thành phố $n$ không thể đến được từ thành phố 1.
Truy vết đường đi: Nếu dp[n] > 0, ta bắt đầu từ thành phố $n$. Dùng mảng parent để đi ngược trở lại: $n \rightarrow parent[n] \rightarrow parent[parent[n]] \rightarrow \dots$ cho đến khi gặp đỉnh 1. Lưu lại các đỉnh này và đảo ngược thứ tự để có đường đi từ 1 đến $n$.

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

Đọc đầu vào: số lượng thành phố $n$, số lượng chuyến bay $m$.
Xây dựng đồ thị bằng danh sách kề (adjacency list).
Tính độ vào (in-degree) cho tất cả các đỉnh.
Khởi tạo mảng dp kích thước $n+1$ với giá trị 0. Đặt dp[1] = 1.
Khởi tạo mảng parent kích thước $n+1$ với giá trị 0.
Khởi tạo hàng đợi cho sắp xếp tô-pô. Thêm tất cả các đỉnh có độ vào bằng 0 vào hàng đợi.
Trong khi hàng đợi chưa rỗng:
- Lấy đỉnh $u$ từ hàng đợi.
- Với mỗi đỉnh $v$ kề với $u$:
  - Nếu dp[u] > 0 (đảm bảo $u$ có thể đến từ 1) VÀ dp[u] + 1 > dp[v]:
    - Cập nhật dp[v] = dp[u] + 1.
    - Cập nhật parent[v] = u.
  - Giảm độ vào của $v$ đi 1.
  - Nếu độ vào của $v$ bằng 0, thêm $v$ vào hàng đợi.
Kiểm tra dp[n]:
- Nếu dp[n] == 0, in ra "IMPOSSIBLE".
- Ngược lại, in ra dp[n] (số lượng thành phố).
Truy vết đường đi:
- Tạo một danh sách rỗng để lưu đường đi.
- Bắt đầu từ đỉnh hiện tại curr = n.
- Trong khi curr != 0:
  - Thêm curr vào đầu danh sách.
  - Cập nhật curr = parent[curr].
- In ra các đỉnh trong danh sách theo thứ tự.

Cấu trúc dữ liệu cần dùng:

vector<vector<int>> adj: Danh sách kề để lưu đồ thị.
vector<int> in_degree: Lưu độ vào của các đỉnh.
vector<int> dp: Mảng DP lưu độ dài đường đi dài nhất (số đỉnh).
vector<int> parent: Mảng lưu vết đỉnh cha để truy vết đường đi.
queue<int> q: Hàng đợi cho sắp xếp tô-pô.

Lưu ý:

Vì đồ thị không có chu trình có hướng, thuật toán sắp xếp tô-pô sẽ xử lý hết tất cả các đỉnh có thể đến từ các đỉnh có độ vào ban đầu bằng 0. Quá trình cập nhật DP dựa trên dp[u] > 0 đảm bảo rằng ta chỉ xem xét các đường đi xuất phát từ (hoặc có thể đến từ) đỉnh 1.
Nếu đỉnh 1 có độ vào lớn hơn 0 nhưng không có đường đi từ các đỉnh có độ vào 0 đến 1, thì 1 sẽ không được thêm vào hàng đợi ban đầu. Tuy nhiên, dp[1] đã được khởi tạo là 1, và nó sẽ được sử dụng để cập nhật các đỉnh kề với 1 khi 1 được xử lý (nếu nó được xử lý sau khi tất cả tiền bối của nó được xử lý và có thể đến từ 1, hoặc nếu nó là đỉnh duy nhất có dp=1). Cách khởi tạo dp[1]=1 và kiểm tra dp[u] > 0 trong vòng lặp xử lý đảm bảo chỉ các đường đi bắt nguồn từ 1 mới được tính độ dài.

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

Comments

There are no comments at the moment.