2 seconds
256 megabytes
A tree is an undirected connected graph without cycles.
Let's consider a rooted undirected tree with n vertices, numbered 1 through n. There are many ways to represent such a tree. One way is to create an array with n integers p1, p2, ..., pn, where pi denotes a parent of vertex i (here, for convenience a root is considered its own parent).
For this rooted tree the array p is [2, 3, 3, 2].
Given a sequence p1, p2, ..., pn, one is able to restore a tree:
- There must be exactly one index r that pr = r. A vertex r is a root of the tree.
- For all other n - 1 vertices i, there is an edge between vertex i and vertex pi.
A sequence p1, p2, ..., pn is called valid if the described procedure generates some (any) rooted tree. For example, for n = 3 sequences(1,2,2), (2,3,1) and (2,1,3) are not valid.
You are given a sequence a1, a2, ..., an, not necessarily valid. Your task is to change the minimum number of elements, in order to get a valid sequence. Print the minimum number of changes and an example of a valid sequence after that number of changes. If there are many valid sequences achievable in the minimum number of changes, print any of them.
The first line of the input contains an integer n (2 ≤ n ≤ 200 000) — the number of vertices in the tree.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).
In the first line print the minimum number of elements to change, in order to get a valid sequence.
In the second line, print any valid sequence possible to get from (a1, a2, ..., an) in the minimum number of changes. If there are many such sequences, any of them will be accepted.
4
2 3 3 4
1
2 3 4 4
5
3 2 2 5 3
0
3 2 2 5 3
8
2 3 5 4 1 6 6 7
2
2 3 7 8 1 6 6 7
In the first sample, it's enough to change one element. In the provided output, a sequence represents a tree rooted in a vertex 4(because p4 = 4), which you can see on the left drawing below. One of other correct solutions would be a sequence 2 3 3 2, representing a tree rooted in vertex 3 (right drawing below). On both drawings, roots are painted red.
In the second sample, the given sequence is already valid.
当时打这场的时候并查集一直歪了（大哭状）所以挂掉了，隔天才补上去的，算是一道并查集的水题吧，多注意点细节就可以了。
思路：
数组a【i】存放的是它所属的父亲，所以有3种情况：
① 当i==a【i】则说明i可以作为最终树的一个根，那么就先把这个根存起来，下次再遇到i==a【i】的情况，直接unite（i，root）并且sum++就可以了；
② 当i！=a【i】&&!same（i，a【i】）时，就直接unite（i，a【i】）;
③ 当i！=a【i】&&same（i，a【i】）时，说明存在环，那么此时先判断根root是否有先找到了。如果没有就直接另root=i并且使a【i】=i，sum++;
而如果根存在的话，就直接a【i】=root，unite（i，root）再sum++。
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
#define mod 998244353
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
int pre[],n,a[],rank[];
void init(int n)
{
for(int i=; i<=n; i++)
{
pre[i]=i;
rank[i]=;
}
}
int find(int x)
{
if(pre[x]==x)
{
return x;
}
else return pre[x]=find(pre[x]);
}
void unite(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
pre[fx]=fy;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}
int main()
{
#ifdef Local
freopen("data.txt","r",stdin);
#endif
int i,j,k,n,m,sum=,root=,p;
cin>>n;
init(n);
for(i=; i<=n; i++)
{
scanf("%d",&a[i]);
if(a[i]==i&&!root)root=i;
}
for(i=; i<=n; i++)
{
if(a[i]==i)
{
if(!root)
{
root=i;
}
else
{
if(i!=root)
{
unite(i,root);
a[i]=root;
sum++;
}
}
}
else
{
if(!same(i,a[i]))unite(i,a[i]);
else
{
if(!root)
{
root=i;
sum++;
a[i]=i;
}
else
{
unite(i,root);
a[i]=root;
sum++;
}
}
}
}
cout<<sum<<endl;
for(i=; i<=n; i++)
{
if(i==n)cout<<a[i]<<endl;
else cout<<a[i]<<" ";
}
return ;
}