Lời giải: Đếm số đường đi giữa hai đỉnh - Nhiều truy vấn

Tư duy

Mỗi truy vấn yêu cầu đếm số đường đi từ \(a_i\) đến \(b_i\) trên bản đồ đảm bảo không vòng khép kín. Vì mỗi truy vấn có thể có cặp \((a_i, b_i)\) khác nhau, ta cần một cách trả lời hiệu quả trên nhiều truy vấn.

Ý tưởng: Quy hoạch động theo thứ tự đảm bảo (topo), lần này duyệt ngược từ đỉnh đích \(b\):

• Đặt \(dp[v]\) là số đường đi từ \(v\) đến \(b\).
• Khởi tạo \(dp[b] = 1\) (đường đi "đứng yên" từ \(b\) đến \(b\)), các \(dp[v]\) khác bằng \(0\).
• Duyệt theo thứ tự đảm bảo đảo ngược (\(b\) xử lý trước, sau đó các đỉnh "trước \(b\)"). Với mỗi đỉnh \(v\): \[dp[v] = \sum_{(v \to w)} dp[w]\] (Vì mỗi đường đi từ \(v\) đến \(b\) phải bắt đầu bằng một bước nhảy sang đỉnh kế tiếp).

Đáp án cho truy vấn \((a, b)\) là \(dp[a]\).

Vì số truy vấn \(Q \le 10^4\) và mỗi truy vấn cần \(O(N + M)\), tổng thời gian là \(O(Q(N + M)) \le 10^9\) — chấp nhận được với C++ đã tối ưu.

Cách giải

1. Tiền xử lý: Đọc đồ thị, sắp xếp theo một thứ tự đảm bảo \(ord\) và tạo ra danh sách đảo ngược \(rord\) (đỉnh đích xử lý trước).
2. Xử lý từng truy vấn:
   • Với \((a, b)\): xây mảng dp[b] = 1, các dp[v] khác bằng \(0\).
   • Duyệt \(rord\). Với mỗi \(v\), cập nhật \(dp[v]\) theo các đỉnh kề sau \(v\) (dùng danh sách cạnh ngược).
   • In ra \(dp[a]\).

Tại sao thuật toán đúng?

• Mỗi đường đi từ \(v\) đến \(b\) phải đi qua đúng một cạnh \(v \to w\) đầu tiên. Phần còn lại là một đường đi từ \(w\) đến \(b\). Theo quy nạp, \(dp[v] = \sum_{w \in N^+(v)} dp[w]\) là đúng.
• Khi duyệt đảo thứ tự đảm bảo ta xử lý \(w\) (đỉnh đi sau \(v\)) trước \(v\), nên \(dp[w]\) đã đúng khi tính \(dp[v]\).

Đánh giá độ phức tạp

• Sắp xếp topo: \(O(N + M)\).
• Mỗi truy vấn: \(O(N + M)\).
• Tổng: \(O(N + M + Q(N + M))\) thời gian, \(O(N + M)\) bộ nhớ.

Mở rộng: Nếu số truy vấn lớn hơn nữa, ta có thể gộp truy vấn theo đích \(b\): tổng thời gian \(O(\#\{\text{đích}\} \cdot (N + M))\) — tối ưu khi nhiều truy vấn cùng đích.

Mã nguồn tham khảo (C++)

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> adj(N + 1), radj(N + 1);
    vector<int> indeg(N + 1, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
        indeg[v]++;
    }
    int Q;
    cin >> Q;
    vector<pair<int,int>> queries(Q);
    for (int i = 0; i < Q; ++i) cin >> queries[i].first >> queries[i].second;

    queue<int> q;
    for (int i = 1; i <= N; ++i) if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }

    for (auto& [a, b] : queries) {
        // dp[v] = so duong di tu v den b
        vector<long long> dp(N + 1, 0);
        dp[b] = 1;
        // duyet nguoc topo
        for (int i = (int)order.size() - 1; i >= 0; --i) {
            int v = order[i];
            if (v == b) continue;
            for (int w : adj[v]) {
                dp[v] = (dp[v] + dp[w]) % MOD;
            }
        }
        cout << dp[a] << "\n";
    }
    return 0;
}