题解 | #谍中谍中谍中谍中谍...#

题目链接

题目描述

有 $n$ 名学生，每名学生 $i$ 指认一名学生 $f_i$ ，形成一张每点出度为 $1$ 的有向图。老师从某个起点开始沿着指认关系不断抓下一位，第一次对某个已经被“警告”过的学生再次“警告”时，该学生自愿退学，过程结束。对每个可能的起点 $s$ ，求最终退学的学生编号。

输入：

第一行一个整数 $n$
第二行 $n$ 个整数 $f_1,\dots,f_n$ ，其中 $f_i$ 为学生 $i$ 指认的学生

输出：

一行 $n$ 个整数，第 $i$ 个表示从 $i$ 出发最终退学的学生编号

解题思路

功能图（每点出度为 $1$ ）由若干环及指向环的入树构成。对于任意起点 $s$ ：

若 $s$ 在环上，则沿着环走一圈后第一次二次“警告”的是 $s$ 自身，答案为 $s$ ；
若 $s$ 不在环上，沿链走到进入某个环的第一个点 $u$ ，之后才会在该环上产生第一次重复，故答案为进入的第一个环点 $u$ （即从 $s$ 可达环的“入口”点）。

据此可在整图上求每个点对应的“环入口”答案：

深搜/迭代遍历并使用三色标记（ $0$ 未访、 $1$ 在栈、 $2$ 已定）。当从 $u$ 沿 $f_u$ 遇到状态为 $1$ 的点 $v$ 时，找到一个环，标记环上所有点的答案为其本身；随后回溯时，树上点的答案等于其后继点的答案。
整体线性时间。

代码

c++
java
python

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

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

    int n; 
    if (!(cin >> n)) return 0;
    vector<int> f(n + 1);
    for (int i = 1; i <= n; ++i) cin >> f[i];

    vector<int> state(n + 1, 0), ans(n + 1, 0), pos(n + 1, -1);
    vector<int> path;
    path.reserve(n);

    for (int s = 1; s <= n; ++s) {
        if (state[s]) continue;
        int u = s;
        while (state[u] == 0) {
            state[u] = 1;
            pos[u] = (int)path.size();
            path.push_back(u);
            u = f[u];
        }
        if (state[u] == 1) {
            int idx = pos[u];
            // mark cycle nodes: answer is themselves
            for (int i = idx; i < (int)path.size(); ++i) {
                int x = path[i];
                ans[x] = x;
                state[x] = 2;
                pos[x] = -1;
            }
            // propagate for nodes before cycle
            for (int i = idx - 1; i >= 0; --i) {
                int x = path[i];
                ans[x] = ans[f[x]];
                state[x] = 2;
                pos[x] = -1;
            }
        } else { // state[u] == 2, reached known segment
            for (int i = (int)path.size() - 1; i >= 0; --i) {
                int x = path[i];
                ans[x] = ans[f[x]];
                state[x] = 2;
                pos[x] = -1;
            }
        }
        path.clear();
    }

    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) f[i] = sc.nextInt();

        int[] state = new int[n + 1]; // 0 unvisited, 1 in-stack, 2 done
        int[] ans = new int[n + 1];
        int[] pos = new int[n + 1];
        Arrays.fill(pos, -1);
        ArrayList<Integer> path = new ArrayList<>(n);

        for (int s = 1; s <= n; s++) {
            if (state[s] != 0) continue;
            int u = s;
            while (state[u] == 0) {
                state[u] = 1;
                pos[u] = path.size();
                path.add(u);
                u = f[u];
            }
            if (state[u] == 1) {
                int idx = pos[u];
                for (int i = idx; i < path.size(); i++) {
                    int x = path.get(i);
                    ans[x] = x;
                    state[x] = 2;
                    pos[x] = -1;
                }
                for (int i = idx - 1; i >= 0; i--) {
                    int x = path.get(i);
                    ans[x] = ans[f[x]];
                    state[x] = 2;
                    pos[x] = -1;
                }
            } else { // state[u] == 2
                for (int i = path.size() - 1; i >= 0; i--) {
                    int x = path.get(i);
                    ans[x] = ans[f[x]];
                    state[x] = 2;
                    pos[x] = -1;
                }
            }
            path.clear();
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(ans[i]);
        }
        System.out.println(sb.toString());
    }
}

import sys
sys.setrecursionlimit(1 << 25)

n = int(input().strip())
f = [0] + list(map(int, input().split()))
state = [0] * (n + 1)  # 0 unvisited, 1 in-stack, 2 done
ans = [0] * (n + 1)
pos = [-1] * (n + 1)

path = []
for s in range(1, n + 1):
    if state[s] != 0:
        continue
    u = s
    while state[u] == 0:
        state[u] = 1
        pos[u] = len(path)
        path.append(u)
        u = f[u]
    if state[u] == 1:
        idx = pos[u]
        for x in path[idx:]:
            ans[x] = x
            state[x] = 2
            pos[x] = -1
        for i in range(idx - 1, -1, -1):
            x = path[i]
            ans[x] = ans[f[x]]
            state[x] = 2
            pos[x] = -1
    else:  # state[u] == 2
        for i in range(len(path) - 1, -1, -1):
            x = path[i]
            ans[x] = ans[f[x]]
            state[x] = 2
            pos[x] = -1
    path.clear()

print(' '.join(map(str, ans[1:])))

算法及复杂度

算法：功能图分解 + 三色标记（检测环并赋值环点，为树上点沿后继传递答案）
时间复杂度： $\mathcal{O}(n)$
空间复杂度： $\mathcal{O}(n)$