Codeforces 755C

本题来自8VC Venture Cup 2017 - Elimination Round，tourist积分榜成绩最高的一场比赛中的第三题

题目大意，有n个数，组成的无向无权图，其中共有n-1条边。
题目第二行给出了n个数，每一个数字表示与第i(1<=i<=n)个节点与那个节点相连，相连数的集合组成了一颗树，请问共有几棵树
例如，n = 5，第二行 2 1 5 3 3 ，则1-2构成一棵树，3-4-5构成一棵树。

代码来自tourist

#include <bits/stdc++.h>

using namespace std;

int main() 
{
	int n;
	scanf("%d", &n);
	set <int> s;
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int foo;
		scanf("%d", &foo);
		if (foo == i) 
			ans++;
		else 
			s.insert(foo);
	}
	printf("%d
", ans + (int) s.size() / 2);
	return 0;
}

第二种传统方法，并查集

#include <bits/stdc++.h>

using namespace std;

const int MAXN=100010;

int par[MAXN];

void init(int n)
{
    for(int i=1;i<=n;i++)
    	par[i]=i;
}

int find(int x)
{
    if(x==par[x])
    	return x;
    return par[x]=find(par[x]);
}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    par[y]=x; 
}

int main()
{
    int n;
    scanf("%d",&n);
    init(n);
    for(int i=1;i<=n;i++)
     {
        int a;
        scanf("%d",&a);
        unite(i,a);
     }
    int ans=0;
    for(int i=1;i<=n;i++)
    	if(i==par[i])
    		ans++;
    printf("%d
",ans); 
    return 0;
}