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

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <set>

using namespace std;
//图的特点是出度全为1，且每个点至多在一个环上，且从点出发路径唯一且经过唯一的环。对于在环上的点就是本身，不在环上就是第一个经过的环上的点
int main () {
	int n;
	cin >> n;
	int* edge = new int[n + 1];
	int* in_degree = new int[n + 1];
	int* ans = new int[n + 1];
	memset(edge, 0, (n + 1) * sizeof(int));
	memset(in_degree, 0, (n + 1) * sizeof(int));
	//ans表示是不是环 
	memset(ans, 0, (n + 1) * sizeof(int));
	for (int i = 1; i <= n; i++) {
		cin >> edge[i];
		in_degree[edge[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		//开始遍历 
		if (!in_degree[i]) {
			int* vis = new int[n + 1];
			memset(vis, 0, (n + 1) * sizeof(int));
			stack<int> s;;
			
			int p = i;
			while (!ans[p] && !vis[p]) {
				vis[p] = 1;
				s.push(p);
				p = edge[p];
			}
			bool flag = (ans[p] && ans[p] == p) ? false : true;
			while (!s.empty()) {
				int p2 = s.top();
				s.pop();
				ans[p2] = flag ? p2 : p;
				if (p == p2) flag = false;
			}
  		}
	}
	for (int i = 1; i <= n; i++) {
		cout << (ans[i] == 0 ? i : ans[i]) << " " ;
	}
}