【c++每天一题】有多少种信仰

描述

学校有?n?个同学，每个同学有且只有一个信仰并且，(1～n)编号，给出?m?对有同一信仰的同学，问存在多少种不同的信仰?

输入描述

输入一个?n?和?m。
以下?m?行，每行输入两个数?a,b，代表?a?同学和?b?同学拥有同一信仰。

输出描述

输出一共有多少种信仰。

样例输入 1?

10 4
2 3
4 5
4 8
5 8

样例输出 1?

7

提示

数据范围与提示

0<n≤50000，0≤m≤n(n?1)/2

这道题采用了并查集的思路，是一道并查集的模板题。话不多说，直接看代码：

#include<iostream>
using namespace std;
int a[50002];
int find(int x){
	if(a[x]==x){
		return x;
	}else{
		return a[x]=find(a[x]);
	}
}
void merge(int x,int y){
	 int fx=find(x);
	 int fy=find(y);
	 a[fx]=fy;
}
int main(){
	long long n,m,x,y,cnt=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		a[i]=i;
	}
	for(int i=0;i<m;i++){
		cin>>x>>y;
		if(find(x)!=find(y)){
		   merge(x,y);
		}
		
	}
	for(int i=1;i<=n;i++){
		if(a[i]==i){
		   cnt++;	
		}
	}
	cout<<cnt;
	return 0;
} 

?

?