rt，是 tarjan 找环的做法。

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

const int N = 2e6 + 5;

int n, a[N], tot, dfn[N], low[N], idx, siz, gld, zh, head[N], eds;
bool vis[N], flag;
vector<int> g[N], pt, G[N];

struct edge
{
	int to, nxt, flag;
} e[N << 1];

inline void addedge(int u, int v)
{
	e[++eds] = {v, head[u], 0};
	head[u] = eds;
}

void dfs(int u, int fa)
{
	vis[u] = 1, siz++;
	for(int i = head[u]; i; i = e[i].nxt)
		if(!vis[e[i].to]) dfs(e[i].to, u);
	return;
}

void tarjan(int u, int fa, int fid)
{
	if(flag) return;
	low[u] = dfn[u] = ++idx;
	if(flag) return;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == u) {zh = u; pt.push_back(u), flag = 1; return;}
		if(flag) return;
		if(!dfn[v])
		{
			tarjan(v, u, i);
			if(flag) return;
			low[u] = min(low[u], low[v]);
		}
		else if(i != (fid ^ 1))
		{
			if(flag) return;
			low[u] = min(low[u], dfn[v]);
			if(flag) return;
			pt.push_back(u), flag = 1; return;
		}
		if(flag) return;	
	}
	if(flag) return;
	return;
}

int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n; eds++;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		addedge(i, a[i]);
		addedge(a[i], i);
	} 
	for(int i = 1; i <= n; i++)
	{
		if(vis[i]) continue;
		siz = 0;
		tot++; dfs(i, 0);
		flag = 0;
		zh = 0;
		tarjan(i, 0, 0);
		if(zh) gld = zh;
		// cout << i << '.';
		if(!flag) pt.push_back(i);
	}
	if(zh)
	{
		// cout << gld << '.';
		cout << tot - 1 << '\n';
		for(int i = 0; i < (int) pt.size(); i++)
			a[pt[i]] = gld;
	}
	else
	{
		cout << tot << '\n';
		for(int i = 0; i < (int) pt.size() - 1; i++)
			a[pt[i]] = pt[i + 1];
		a[pt.back()] = pt.back();
	}
	for(int i = 1; i <= n; i++) cout << a[i] << ' ';
	return 0;
}