描述
学校有 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
这道题采用了并查集的思路，是一道并查集的模板题。话不多说，直接看代码：文章来源：https://www.toymoban.com/news/detail-797322.html
#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;
}
文章来源地址https://www.toymoban.com/news/detail-797322.html
到了这里，关于【c++每天一题】有多少种信仰的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
