Fix a Tree

Fix a Tree

http://codeforces.com/problemset/problem/698/B
题意:无向图中:给n,表示有1~n个节点,紧接着按顺序给出1~n节点对应的一个邻接点
要求通过改变某些顶点的邻接点,使得无向图成为一颗无向树(其中,根有一条指
向自己的边,也就是说它的邻接点必须是自己;最后,给出最小更改次数和满足要求后
1~n号节点的邻接点.
思路:无向树:无环连通图;这里要有一个自环; 用并查集可以判断是否连通,同时,
在加边过程中也可以通过判断是否连通以判断该边是否属于重边;
把所有重边记录下来进行更改(如果是根的边则不用更改)使得更改后的边连接两个
原来属于不同连通分量(并查集)的顶点;
这样可以得到一颗满足要求的树,但是更改次数却不一定是最小的;为了最快解决,可以
试着寻找一个满足作为根的顶点,不对由根指向根的边进行更改而后其他重边进行更改,
可以保证次数最小;为什么说试着?显然,可能不存在这样的顶点,那么就每次选择重边进行更改就行.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>

using namespace std;
const int maxn=200100;
int par[maxn];//并查集
int n,data[maxn];
set<int> more;//重边起点
void init()
{
    par[0]=-1;
    for (int i=1; i<=n; i++)
        par[i]=i;//将所有顶点作为一个独立的连通分量
    more.clear();
}
int findp(int x)
{
    if(x==par[x]) return x;//根
    return par[x]=findp(par[x]);//优化查找
}
void unit(int a,int b)
{
    a=findp(a);
    b=findp(b);
    if(a==b) return;
    else par[b]=a;//这里合并无需计较高度,因为在每次查找时,会把高度变为1
}
int main()
{
    while (scanf("%d",&n)==1)
    {
        init();
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&data[i]);
            if (findp(i)!=findp(data[i])) unit(data[i],i);//不连通的顶点,加了边后应合并在一个连通分量
            else more.insert(i);//重边起点
        }
        int cnt=0,r=0;
        set<int>::iterator itm=more.begin();
        for(; itm!=more.end(); itm++)
        {
            if (data[*itm]==*itm)//试着找根
                r=*itm;
        }
        if (!r)//找不到根
            r=*more.begin();//随便用一条重边的起点作为根
        for (itm=more.begin(); itm!=more.end(); itm++)
        {
            if (findp(*itm)!=findp(r))//排除根与属于其他连通分量的顶点合并
            {
                cnt++;
                par[*itm]=r;
                data[*itm]=r;
            }
            else if (data[*itm]!=*itm)//根并未指向自己
            {
                cnt++;
                par[*itm]=*itm;
                data[*itm]=*itm;
            }
        }
//输出
        printf("%d\n%d",cnt,data[1]);
        for (int i=2; i<=n; i++)
        {
            printf(" %d",data[i]);
        }
        printf("\n");

    }
    return 0;
}