Hướng giải của Số Bước Để Đến V

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải: Số Bước Để Đến V

Phân tích bài toán

Yêu cầu tính số bước tối thiểu đi từ \(U\) tới \(V\) trên một đồ thị hàm số. Nhận xét: Mỗi thành phần liên thông của đồ thị hàm số chỉ có đúng một chu kỳ duy nhất, và các đỉnh không thuộc chu kỳ sẽ tạo thành các nhánh cây đi vào chu kỳ đó.

  1. Ta sử dụng thuật toán loang/DFS ngược để phân tích cấu trúc đồ thị trong thời gian \(O(N)\):
    • Xác định mã số thành phần liên thông comp_id.
    • Tìm các đỉnh thuộc chu kỳ và đánh số thứ tự của chúng trong chu kỳ cycle_idx (từ \(0\) đến \(L-1\)).
    • Với mỗi đỉnh \(i\) trong các nhánh cây, ta xác định độ sâu depth[i] (khoảng cách tới chu kỳ) và đỉnh vào chu kỳ của nó cycle_node[i].
  2. Trả lời truy vấn:
    • Nếu \(U\) và \(V\) thuộc hai thành phần khác nhau \(\to\) -1.
    • Nếu \(V\) nằm trong nhánh cây (depth[v] > 0): Ta chỉ có thể đi tới \(V\) nếu \(V\) là tổ tiên trực tiếp của \(U\) trên nhánh cây. Ta kiểm tra điều này bằng cách nhảy nhị phân depth[u] - depth[v] bước từ \(U\) xem có tới được \(V\) hay không.
    • Nếu \(V\) nằm trong chu kỳ (depth[v] == 0): \(U\) luôn đi tới được \(V\). Số bước đi là số bước từ \(U\) tới chu kỳ depth[u] cộng với khoảng cách xoay vòng trên chu kỳ từ cycle_node[u] tới \(V\) (bằng (cycle_idx[v] - cycle_idx[root_u] + L) % L).
Độ phức tạp
  • Thời gian: \(O(N \log N)\) tiền xử lý (để xây dựng bảng Binary Lifting) và \(O(\log N)\) mỗi truy vấn (trong trường hợp phải nhảy nhị phân kiểm tra tổ tiên).
  • Không gian: \(O(N \log N)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;

    int LOG = 20;
    vector<vector<int>> up(n, vector<int>(LOG));
    vector<int> nxt(n);
    vector<vector<int>> radj(n);
    for (int i = 0; i < n; i++) {
        cin >> nxt[i];
        up[i][0] = nxt[i];
        radj[nxt[i]].push_back(i);
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    vector<int> vis(n, 0);
    vector<int> comp_id(n, -1);
    vector<int> cycle_node(n, -1);
    vector<int> depth(n, -1);
    vector<int> cycle_idx(n, -1);
    vector<int> cycle_len;

    int comp_counter = 0;

    for (int i = 0; i < n; i++) {
        if (vis[i] == 0) {
            int curr = i;
            vector<int> path;
            while (vis[curr] == 0) {
                vis[curr] = 1;
                path.push_back(curr);
                curr = nxt[curr];
            }
            if (vis[curr] == 1) {
                int cid = comp_counter++;
                auto it = find(path.begin(), path.end(), curr);
                vector<int> cycle(it, path.end());
                cycle_len.push_back(cycle.size());
                for (int idx = 0; idx < (int)cycle.size(); idx++) {
                    int node = cycle[idx];
                    comp_id[node] = cid;
                    cycle_node[node] = node;
                    depth[node] = 0;
                    cycle_idx[node] = idx;
                }

                queue<int> mq;
                for (int node : cycle) {
                    mq.push(node);
                }
                while (!mq.empty()) {
                    int u = mq.front();
                    mq.pop();
                    for (int v : radj[u]) {
                        if (depth[v] == -1) {
                            comp_id[v] = cid;
                            cycle_node[v] = cycle_node[u];
                            depth[v] = depth[u] + 1;
                            mq.push(v);
                        }
                    }
                }
            }
            for (int node : path) {
                vis[node] = 2;
            }
        }
    }

    auto get_k_successor = [&](int node, int k) {
        for (int j = 0; j < LOG; j++) {
            if (k & (1 << j)) {
                node = up[node][j];
            }
        }
        return node;
    };

    while (q--) {
        int u, v;
        cin >> u >> v;
        if (comp_id[u] != comp_id[v]) {
            cout << -1 << "\n";
            continue;
        }
        int cid = comp_id[u];

        if (depth[v] > 0) {
            if (cycle_node[u] == cycle_node[v] && depth[u] >= depth[v] && get_k_successor(u, depth[u] - depth[v]) == v) {
                cout << depth[u] - depth[v] << "\n";
            } else {
                cout << -1 << "\n";
            }
        } else {
            int ans = depth[u];
            int root_u = cycle_node[u];
            int L = cycle_len[cid];
            int on_cycle_dist = (cycle_idx[v] - cycle_idx[root_u] + L) % L;
            cout << ans + on_cycle_dist << "\n";
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.