Codeup 并查集之问题 D: More is better

Love The Way You Lie 2023-02-14 02:29 17阅读 0赞

#### 分析 ####

本题要求我们算出每个集合中的元素个数，然后输出元素个数的最大值

**元素个数的计算，我采用的思路是：**  
noc数组记录结点拥有的孩子结点数  
遍历每个结点，找到他的根结点，将noc【ff（ i ）】递增  
每次递增完判别一下是否大于max，是则更新，最后输出max即可

#include<iostream>
    using namespace std;
    int father[100005];
    int noc[100005];
    void init()
    { 
        for(int i=1;i<100005;i++)
        { 
            father[i]=i;
            noc[i]=0;
        }
    }
    int ff(int a)
    { 
        int b=a;
        while(a!=father[a])
        { 
            a=father[a];
        }
        while(b!=father[b])
        { 
            int c=b;
            b=father[b];
            father[c]=a;
        }
        return a;
    }
    void Union(int a,int b)
    { 
        int fa=ff(a);
        int fb=ff(b);
        if(fa!=fb)
        { 
            father[fa]=fb;
        }
    }
    int main()
    { 
        int n;
        while(cin>>n)
        { 
            int a,b;
            init();
            for(int i=0;i<n;i++)
            { 
                cin>>a>>b;
                Union(a,b);
            }
            int max=0;
            for(int i=1;i<=100000;i++)
            { 
                noc[ff(i)]++;
                if(noc[ff(i)]>max)max=noc[ff(i)];
            }
            cout<<max<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 More is better 查并集并且找最大连通分量

<table> <tbody> <tr> <td> <h2>More is better</h2> <strong>Time Limit: 5000/1000

左手的ㄟ右手/ 2024年02月18日 22:54/ 0 赞/ 105 阅读

相关 Codeup 并查集之问题 D: More is better

分析本题要求我们算出每个集合中的元素个数，然后输出元素个数的最大值元素个数的计算，我采用的思路是： noc数组记录结点拥有的孩子结点数遍历每个结点，找到他

Love The Way You Lie/ 2023年02月14日 02:29/ 0 赞/ 18 阅读

相关 Codeup 并查集之问题 C: How Many Tables

题目翻译：今天是小明的生日。他邀请了很多的朋友。到了吃晚饭的时间，小明想要知道他至少需要多少张桌子。你需要注意并不是小明所有的朋友都互相认识，并且他们都不想自己和陌生人

曾经终败给现在/ 2023年02月14日 02:26/ 0 赞/ 18 阅读

相关 Codeup 并查集之问题 B: 畅通工程

分析我们可以把有道路能达到的两个城市看作一个连通块，那么题中要求的就是连通块的数量。假设有n个连通块，那么只需要在两个连通块间建一条路就可以满足要求，因此最后输出

骑猪看日落/ 2023年02月14日 02:25/ 0 赞/ 82 阅读

相关 Codeup 并查集之问题 A: 通信系统

思路：利用并查集建立起端点与端点的关系题目要求： 1.某个端点生成后，其余各个端点均能接收到消息这句话转换到并查集的思想就是所有的端点应该在一个集合之中

柔情只为你懂/ 2023年02月14日 02:11/ 0 赞/ 88 阅读

相关 HDU 1856 -More is better

并查集rank数组 Description Mr Wang wants some boys to help him with a project. Because

本是古典何须时尚/ 2022年08月21日 11:58/ 0 赞/ 80 阅读

相关 More is better--hdu1856（并查集）

More is better Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 327680/102400 K (Ja

柔光的暖阳◎/ 2022年08月04日 08:54/ 0 赞/ 58 阅读

相关 HDU 1856 More is better （并查集基本操作）

Mr Wang wants some boys to help him with a project. Because the project is rather comple

末蓝、/ 2022年06月13日 13:58/ 0 赞/ 161 阅读

相关 D - More is better

题目描述： Mr Wang wants some boys to help him with a project. Because the project is rath

缺乏、安全感/ 2022年03月19日 11:26/ 0 赞/ 196 阅读

相关 More is better(并差集)

More is better Problem Description Mr Wang wants some boys to help him with a project

叁歲伎倆/ 2022年02月25日 13:14/ 0 赞/ 230 阅读