7-15 Disjoint Set (14 分)
Disjoint Set(Or Union-Find) can be used to check whether an undirected graph contains cycle or not. Note that we have discussed the Kruskal algorithm to detect cycle. This is the method based on Union-Find.
Input Specifcation:
There are n students and m relations in first line(n<1000, m<2000), there are m lines following, there are two numbers(a and b) in each line, that means a and b are in the same classes.
Output Specifcation:
How many classes are there in the n students?
Input Example:
5 3 1 2 2 4 3 4
Output Example:
2
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<bits/stdc++.h>
using namespace std;
int f[1000];
int fun(int x){
int fa;
if(f[x]==x)
return x;
else
return f[x]=fun(f[x]);
}
int main(){
int n,m,i,a,b;
int c,d;
cin>>n>>m;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++){
cin>>a>>b;
c=fun(a);
d=fun(b);
if(c!=d)
f[d]=c;
}
int result=0;
for(i=1;i<=n;i++){
if(f[i]==i)
result++;
}
cout<<result;
return 0;
}