文章

13

粉丝

168

获赞

13

访问

16.9k

头像
模板题
P1319 浙江大学机试题
发布于2023年6月22日 22:09
阅读数 1.2k

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发