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

Myth丶恋晨 2021-09-30 16:30 226阅读 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 条评论，226人围观）

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

相关阅读

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

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

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

相关亲戚(洛谷)---简单并查集

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

待我称王封你为后i/ 2023年07月09日 06:27/ 0 赞/ 1 阅读

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

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

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

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

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

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

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

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

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 545 阅读