文章
13
粉丝
168
获赞
13
访问
16.9k
#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s;i<e;i++)
#define per(i,s,e) for(int i=s;i>e;i--)
using namespace std;
#define MAXN 1005
int fa[MAXN];//fa[x]是x的父节点,初始化设为自己
void init(int n){//初始化每个节点的父节点为他自己
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int i){
if(i==fa[i])
return i;
else{
fa[i]=find(fa[i]);//该步进行了路径压缩:存储i的祖先为i的父节点
return fa[i];//返回父节点
}
}
void unionn(int i,int j){//合并i和j所在集合,i_fa指向j_fa
int i_fa=find(i);//查找i的祖先i_fa
int j_fa=find(j);//查找j的祖先j_fa
fa[i_fa]=j_fa;//将j和i的祖先合并
}
int main() {
//求有用于联通未联通集合的路径数sum
int M,N,sum,x,y,fa_x,fa_y;
while(cin>>N){
if(N==0) break;
cin>>M;
init(N);
sum=0;
for(int i=0;i<M;i++){
cin>>x>>y;
fa_x=find(x);
fa_y=find(y);
if(fa_x!=fa_y){
unionn(fa_x,fa_y);//增加一条路径,联通两个集合
sum++;//这种路径数量+1
}
} cout<<N-sum-1<<endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发