首页 > 代码库 > PAT A 1118. Birds in Forest (25)
PAT A 1118. Birds in Forest (25)
并查集合并
#include<iostream>using namespace std;const int MAX = 10010;int father[MAX],root[MAX];int findfather(int x){ if(x==father[x]) return x; else{ int F=findfather(father[x]); father[x]=F; return F; }}void Union(int a , int b){ int faA=findfather(a); int fbB=findfather(b); if(faA!=fbB){ father[faA]=fbB; } }void init(){ for(int i=0;i<MAX;i++){ father[i]=i; root[i]=0; }} int n,q;int main(){ init(); cin>>n; int maxbirds=0; for(int i=0;i<n;i++){ int nbirds,firstbird; scanf("%d%d",&nbirds,&firstbird); if(firstbird>maxbirds) maxbirds=firstbird; for(int j=1;j<nbirds;j++){ int bird; scanf("%d",&bird); if(bird>maxbirds) maxbirds=bird; Union(firstbird,bird); } } int trees=0; for(int i=1;i<=maxbirds;i++){ int fa=findfather(i); root[fa]++; if(root[fa]==1) trees++; } printf("%d %d\n",trees,maxbirds); cin>>q; while(q--){ int a , b; scanf("%d%d",&a,&b); if(findfather(a)==findfather(b)) printf("Yes\n"); else printf("No\n"); }}
非递归压缩并查集
int father[MAX]; bool isRoot[MAX];//判根 int findFather( int x ) { int a = x; while( x != father[x] ) { x = father[x]; } while( a != father[a] ) { int z = a; a = father[a]; father[z] = x; } return x; } void Union( int a, int b ) { int faA = findFather( a ); int faB = findFather( b ); if( faA != faB ) { father[faA] = faB; } } void init( int n ) { for( int i = 1; i <= n; i++ ) { //从1开始 father[i] = i; isRoot[i] = false; } }
PAT A 1118. Birds in Forest (25)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。