首页 > 代码库 > 洛谷P1551亲戚 并查集
洛谷P1551亲戚 并查集
洛谷P1551亲戚 并查集 按秩合并 + 路径压缩
#include <bits/stdc++.h> using namespace std ; const int N = 5011 ; int fa[N],rk[N] ; int n,m,Q ; inline void init() { for(int i=1;i<=n;i++) fa[ i ] = i,rk[ i ] = 1 ; } inline int find(int x) { if(x==fa[ x ]) return x ; return fa[ x ] = find(fa[ x ]) ; } inline void Union(int x,int y) { x = find(x) ; y = find(y) ; if(x==y) return ; if(rk[ x ] < rk[ y ]) // 并查集 按秩合并 fa[ x ] = y ; // 按照深度大小合并,实际上也是按照子树大小合并 else { fa[ y ] = x ; if(rk[ x ]==rk[ y ]) rk[ x ]++ ; } } int main() { scanf("%d%d%d",&n,&m,&Q) ; init() ; int x,y ; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y) ; Union(x,y) ; } for(int i=1;i<=Q;i++) { scanf("%d%d",&x,&y) ; if(find( x )==find( y )) printf("Yes\n") ; else printf("No\n") ; } return 0 ; }
洛谷P1551亲戚 并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。