8VC Venture Cup 2017 - Elimination Round - C

题目链接：http://codeforces.com/contest/755/problem/C

题意：PolandBall 生活在一个森林模型的环境中，定义森林由若干树组成，定义树为K个点，K-1条无向边的图。现在给定每个家庭在对应的树上离他最远的另一个家庭的编号。问这个森林有多少棵树组成。

思路：由于只给出了每个点在树上离他最远的点的坐标而不知道整体结构，但是可以知道该点和给定离他最远的点一定是在同一颗树上，所以维护一个并查集，最后有多少个连通分量就是有多少棵树了。

import java.io.PrintWriter;

import java.util.*;

public class Main {

    public static final int MAXN=10000+10;

    public static int fa[]=new int [MAXN];

    public static int ans;

    public static int find(int x){

        return x==fa[x] ? (fa[x]) : (fa[x]=find(fa[x]));

    }

    public static void Union(int x,int y){

        int rootx=find(x),rooty=find(y);

        if(rootx==rooty)

        {

            return;

        }

        fa[rooty]=rootx;

        ans--;

    }

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);

        PrintWriter out = new PrintWriter(System.out);

        int n=cin.nextInt(); ans=n;

        for(int i=1;i<=n;i++){

            fa[i]=i;

        }

        for(int i=1;i<=n;i++){

            Union(i,cin.nextInt());

        }

        out.println(ans);

        cin.close();

        out.flush();

    }

}