【题解】P15108 白井黑子

ExplodingKonjac · 2026-02-01 18:02:36 · 题解

【原题链接】

题目分析

注意到题目给了我们两个数组，又注意到两个数组可以维护一个双向链表，所以注意到我们可以用链表维护出 DFS 序。

不引起歧义地，以下我们将维护 DFS 序的链表简称为链表。

算法过程中，我们让 f 链表的前驱数组，a 是链表的后继数组。

我们枚举 i = 1, 2, \dots, n。每次枚举到一个未被访问的点 i 时，我们可以一直跳父亲，直到跳到一个已访问的点为止。我们令这些点在链表中为连续一整段，这样 f_i 的值可以直接使用，a_i 也可以求出来。于是我们得到一条链。设链顶的父亲（那个跳到的已访问的点）是 v，显然我们可以直接把整条链插入到链表中 v 的后面。

最后，从根开始跳后继，先把答案存在 f 中，最后拷贝到 a 中。

代码实现

这里使用 a_i \neq 0 判断 i 已访问，使用 a_i = i 表示 i 是末尾节点。

void dfs(int n, Array& f, Array& a) {
    int rt = -1;
    for (int i{1}; i <= n; i++) {
        if (a[i]) continue;
        a.set(i, i);
        for (int u{i};; u = f[u]) {
            int v = f[u];
            if (v == 0) {
                rt = u;
                break;
            } else if (a[v]) {
                int x = a[v];
                if (x != v) {
                    a.set(v, u), f.set(u, v);
                    a.set(i, x), f.set(x, i);
                } else {
                    a.set(v, u), f.set(u, v);
                }
                break;
            } else {
                a.set(v, u);
            }
        }
    }
    for (int u{rt}, k = 0;; u = a[u]) {
        f.set(++k, u);
        if (a[u] == u) break;
    }
    for (int k{1}; k <= n; k++) {
        a.set(k, f[k]);
    }
}