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

题目链接

题目描述

有 $n$ 名学生（编号 $1$ 到 $n$ ），每位学生 $i$ 都会指认一名学生 $p_i$ 作为带头人。老师从任意一名学生开始警告，然后根据指认关系一路警告下去，直到第一次遇到一名已经被警告过的学生。这名被重复警告的学生将被劝退。

任务是，对于每个可能的起始学生 $i$ （从 $1$ 到 $n$ ），找出最终被劝退的学生是谁。

解题思路

这个问题可以被模型化为一个函数图（functional graph）。在这张图中，每个节点（学生）都恰好有一条出边（指向其指认的学生）。这种图的结构特点是，它由一个或多个互不相连的组件构成，而每个组件都包含一个有向环，以及一些指向这个环的树状结构。

当老师从一个学生 $s$ 开始沿着指认关系链条前进时，他实际上是在图上遍历一条路径。由于节点数量有限，这条路径最终必然会进入一个环。

根据题意，被劝退的学生是这条路径上第一个被重复访问的节点。

如果起始学生 $s$ 本身就在一个环上，那么当老师沿着环走一圈回到 $s$ 时， $s$ 就是第一个被重复访问的节点。因此，对于环上的任意节点，最终被劝退的就是它自己。
如果起始学生 $s$ 在一个指向环的树状结构上，那么路径会先经过树上的节点，最终进入环。路径上第一个进入的环上节点，将是这条路径上第一个被重复访问的节点。因此，对于树上的任意节点，最终被劝退的都是它所指向的那个环的入口节点。

一个一个模拟每个起始点，时间复杂度会达到 $O(n^2)$ ，对于 $n$ 的规模来说太慢了。我们可以采用一个更高效的记忆化方法，确保每个节点只被访问一次，从而将总时间复杂度优化到 $O(n)$ 。

算法步骤如下：

创建一个答案数组 ans，用于存放每个学生的最终结果，初始时所有值都设为 0，表示尚未计算。
遍历所有学生 $i$ （从 $1$ 到 $n$ ）。
如果学生 $i$ 的答案 ans[i] 仍为 0，说明我们还没有处理过包含 $i$ 的这个组件，于是从 $i$ 开始进行路径追踪。
在追踪过程中，记录下当前路径上的所有节点。追踪会一直持续，直到遇到以下两种情况之一：

a. 我们遇到了一个节点 curr，它的答案 ans[curr] 已经计算出来了。这意味着当前路径最终汇入了另一个已经处理过的组件。那么，当前路径上所有节点的答案都和 curr 的答案相同。我们据此更新 ans 数组即可。

b. 我们遇到了一个节点 curr，它已经在当前路径中出现过了。这说明我们找到了一个新的环。此时，环上的每个节点，其最终答案就是它自己；而路径上通向环的“尾巴”部分的所有节点，其最终答案都是环的入口节点（即 curr）。我们据此更新 ans 数组。
由于每个学生的答案一旦被计算出来就不会再改变，这个过程保证了每个学生只会被访问一次。遍历完所有学生后，ans 数组就包含了所有起始情况的最终结果。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    vector<int> ans(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        if (ans[i] == 0) {
            vector<int> path;
            map<int, int> path_indices;
            int curr = i;

            while (ans[curr] == 0 && path_indices.find(curr) == path_indices.end()) {
                path_indices[curr] = path.size();
                path.push_back(curr);
                curr = p[curr];
            }

            if (ans[curr] != 0) {
                // 情况a: 路径汇入一个已处理的组件
                int final_node = ans[curr];
                for (int node : path) {
                    ans[node] = final_node;
                }
            } else {
                // 情况b: 发现新环
                int cycle_start_index = path_indices[curr];
                
                // 处理环前的尾巴
                for (int j = 0; j < cycle_start_index; ++j) {
                    ans[path[j]] = curr;
                }
                // 处理环
                for (int j = cycle_start_index; j < path.size(); ++j) {
                    ans[path[j]] = path[j];
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

        int[] p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }

        int[] ans = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (ans[i] == 0) {
                ArrayList<Integer> path = new ArrayList<>();
                Map<Integer, Integer> pathIndices = new HashMap<>();
                int curr = i;

                while (ans[curr] == 0 && !pathIndices.containsKey(curr)) {
                    pathIndices.put(curr, path.size());
                    path.add(curr);
                    curr = p[curr];
                }

                if (ans[curr] != 0) {
                    // 情况a: 路径汇入一个已处理的组件
                    int finalNode = ans[curr];
                    for (int node : path) {
                        ans[node] = finalNode;
                    }
                } else {
                    // 情况b: 发现新环
                    int cycleStartIndex = pathIndices.get(curr);

                    // 处理环前的尾巴
                    for (int j = 0; j < cycleStartIndex; j++) {
                        ans[path.get(j)] = curr;
                    }
                    // 处理环
                    for (int j = cycleStartIndex; j < path.size(); j++) {
                        ans[path.get(j)] = path.get(j);
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(ans[i] + (i == n ? "" : " "));
        }
        System.out.println();
    }
}

import sys

def main():
    n_str = sys.stdin.readline()
    if not n_str:
        return
    n = int(n_str)
    
    line = sys.stdin.readline()
    if not line:
        return
    p = [0] + list(map(int, line.split()))

    ans = [0] * (n + 1)

    for i in range(1, n + 1):
        if ans[i] == 0:
            path = []
            path_indices = {}
            curr = i

            while ans[curr] == 0 and curr not in path_indices:
                path_indices[curr] = len(path)
                path.append(curr)
                curr = p[curr]

            if ans[curr] != 0:
                # 情况a: 路径汇入一个已处理的组件
                final_node = ans[curr]
                for node in path:
                    ans[node] = final_node
            else:
                # 情况b: 发现新环
                cycle_start_index = path_indices[curr]
                
                # 处理环前的尾巴
                for j in range(cycle_start_index):
                    ans[path[j]] = curr
                # 处理环
                for j in range(cycle_start_index, len(path)):
                    ans[path[j]] = path[j]

    print(*ans[1:])

if __name__ == "__main__":
    main()

算法及复杂度

算法：函数图寻环与路径分析。通过记忆化的方式遍历图，避免重复计算。
时间复杂度： $O(n)$ ，因为每个节点只会被访问和处理一次。
空间复杂度： $O(n)$ ，用于存储指认关系 $p$ 、答案数组 ans 以及单次遍历中最长的路径。