【codevs1073/P1551】家族/亲戚——并查集

Myth丶恋晨 2021-09-30 16:30 224阅读 0赞

题目链接：[codevs][]，[洛谷][Link 1]

--------------------

这道题就是并查集的基础题，getf函数寻找该节点的祖先，要注意在查找的时候可以顺便把路上的节点的父节点也改为当前祖先（即路径压缩）。

询问的时候不能因为两个点的父节点不同就说他们不是同一棵树上的，要一直找到他们的祖先再做比较。

具体实现细节看代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    using namespace std;
    int f[5005];
    int read()
    {
        int ans=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
        return ans*f;
    }
    int getf(int x)
    {
        if(f[x]==x)return x;
        f[x]=getf(f[x]);
        return f[x];
    }
    void fa(int x,int y)
    {
        int x0=getf(x),y0=getf(y);
        if(x0==y0)return ;
        f[y0]=x0;
    }
    int main()
    {
        int n=read(),m=read(),p=read(),ai,bi;
        for(int i=1;i<=n;i++)f[i]=i;
        for(int i=1;i<=m;i++){
            ai=read();bi=read();
            fa(ai,bi);
        }
        for(int i=1;i<=p;i++)
        {
            ai=read();bi=read();
            int x0=getf(ai),y0=getf(bi);
            if(x0==y0)printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }

code1073/洛谷P1551

转载于:https://www.cnblogs.com/JKAI/p/7277845.html

[codevs]: http://codevs.cn/problem/1073/
[Link 1]: https://www.luogu.org/problem/show?pid=1551#sub
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210724/16a3f6eb592349ae8a4b6ac985ac4216.png

发表评论取消回复

表情：

评论列表（有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

相关 codevs1001 舒适的路线贪心枚举+并查集

题目描述 Description Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。 Z小镇附近共有 N(1<N≤500)个景点（编号为1,2,3,…,N

旧城等待，/ 2024年02月17日 19:50/ 0 赞/ 10 阅读

相关 codevs1069 关押罪犯贪心+并查集

题目描述 Description S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随

不念不忘少年蓝@/ 2024年02月17日 19:48/ 0 赞/ 41 阅读

相关 Vijos P1034家族【基础并查集】

P1034家族未递交标签： \[显示标签\] 描述若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否

清疚/ 2022年08月18日 02:12/ 0 赞/ 117 阅读

相关【日常学习】【并查集+map】codevs2639 约会计划题解

然而我竟然让诸城一中悲剧机房的C++能够编译了··· 直接上题目题目描述 Description cc是个超级帅哥，口才又好，rp极高（这句话似乎降rp），又非常的幽默

爱被打了一巴掌/ 2022年08月02日 15:59/ 0 赞/ 7 阅读

相关 1073 家族（并查集模板）

题目描述 Description 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲

﹏ヽ暗。殇╰゛Y/ 2022年06月15日 00:37/ 0 赞/ 144 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 277 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 287 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 345 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 339 阅读

相关【codevs1073/P1551】家族/亲戚——并查集

题目链接：[codevs][]，[洛谷][Link 1] -------------------- 这道题就是并查集的基础题，getf函数寻找该节点的祖先

Myth丶恋晨/ 2021年09月30日 16:30/ 0 赞/ 225 阅读