并查集

并查集

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:
合并(Union):把两个不相交的集合合并为一个集合。
查询(Find):查询两个元素是否在同一个集合中。

初始化:

fa[i]=i;

Find:

无压缩

int Find(int x) {
    if(fa[x]==x) return x;
    else return Find(fa[x]);
}

压缩

int Find(int x) {
//    if(x!=fa[x]) fa[x]=Find(fa[x]);
//    return fa[x];
    return x==fa[x] ? x : (fa[x]=Find(fa[x]));//简写
}

Union:

void Union(int x,int y) {
    fa[Find(x)]=Find(y);
}

例(洛谷P1551):

https://www.luogu.com.cn/problem/P1551

#include<bits/stdc++.h>
using namespace std;
int fa[5005];
int Find(int x) {
//    if(x!=fa[x]) fa[x]=Find(fa[x]);
//    return fa[x];
    return x==fa[x] ? x : (fa[x]=Find(fa[x]));
}
void Union(int x,int y) {
    fa[Find(x)]=Find(y);
}
int main() {
    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i) {
        int x,y;
        cin>>x>>y;
        Union(x,y);
    }
    for(int i=1;i<=p;++i) {
        int x,y;
        cin>>x>>y;
        if(Find(x)==Find(y)) {
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
} 
全部评论

相关推荐

风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务