1. Johngo学长首页
  2. 技术点详细复盘专题
  3. Linux

POJ1611(The Suspects)–简单并查集

• Linux • 阅读 117 
  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include
  8 #include<set>
  9 #include
 10 #include
 11 #include<string>
 12 #include
 13 #include
 14 using namespace std;
 15 #define MAX 100
 16
 17 struct node
 18 {
 19     int no;//编号
 20     int rank;
 21     int parent;
 22     int total;
 23 };
 24
 25 class DisJoinSet
 26 {
 27     protected:
 28         int n;
 29         node * tree;
 30     public:
 31         DisJoinSet(int n );
 32         ~DisJoinSet();
 33         void Init();
 34         void Union(int x,int y);
 35         int Find(int x);
 36         int GetAswer(int x);
 37 };
 38
 39 DisJoinSet ::DisJoinSet(int  n)//初始化操作
 40 {
 41     this->n = n;
 42     tree = new node[n];
 43     for(int i = 0 ; i < n; i++)
 44     {
 45         tree[i].no = i;
 46         tree[i].parent = i;
 47         tree[i].total = 1;
 48         tree[i].rank = 0;
 49     }
 50 }
 51 DisJoinSet::~DisJoinSet()
 52 {
 53     delete[] tree;
 54 }
 55
 56 void DisJoinSet :: Init()
 57 {
 58 }
 59 int DisJoinSet::Find(int x)
 60 {
 61     int temp = tree[x].parent;//temp 为x的父亲结点
 62     if( x != tree[x].parent)
 63     {
 64         tree[x].parent = Find(tree[x].parent);//路径压缩
 65         return tree[x].parent;
 66     }
 67     else
 68     {
 69         return x;
 70     }
 71 }
 72
 73 void DisJoinSet ::Union(int x,int y)
 74 {
 75     int rootx = Find(x);
 76     int rooty = Find(y);
 77     if(rootx == rooty)
 78     {
 79         return ;
 80     }
 81     else//并查集基本操作
 82     {
 83         if(tree[rootx].rank < tree[rooty].rank)
 84         {
 85             tree[rootx].parent = rooty;
 86             tree[rooty].total += tree[rootx].total;
 87         }
 88         else
 89         {
 90             tree[rooty].parent = rootx;
 91             tree[rootx].total += tree[rooty].total;
 92             if(tree[rootx].rank == tree[rooty].rank)
 93             {
 94                 tree[rootx].rank++;
 95             }
 96         }
 97     }
 98 }
 99
100 int DisJoinSet::GetAswer(int x)//返回xtotal
101 {
102     int t = Find(x);
103     return tree[t].total;
104 }
105
106 int main()
107 {
108     int n;
109     int m;
110     while(cin>>n>>m && n!=0 && m>= 0)
111     {
112         DisJoinSet dis(n);
113         int per1;
114         int per2;
115         for(int i = 0; i< m;i++)
116         {
117             int num = 0;
118             cin>>num;
119             cin>>per1;
120             for(int i = 1 ;i < num; i++)
121             {
122                 cin>>per2;
123                 dis.Union(per1,per2);
124             }
125         }
126         cout<0)<<endl;
127     }
128     return 0;
129 }(

Original: https://www.cnblogs.com/ygsworld/p/11256729.html
Author: 回忆酿的甜
Title: POJ1611(The Suspects)–简单并查集

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582148/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

  • python截取字符串(字符串切片)

    python中使用 []来截取字符串，语法： &#x5B57;&#x7B26;&#x4E32;[&#x8D77;&#x59CB;&#…

    Linux 2023年6月6日
    0132

  • [ Skill ] 如何获取库中的 top cell

    https://www.cnblogs.com/yeungchie/ top cell 的一个特点就是没有被其他的单元所调用，下面举例获取某个库中的 top cell。 1. 获取…

    Linux 2023年6月7日
    0104

  • Tensorflow-逻辑斯蒂回归

    1.交叉熵 逻辑斯蒂回归这个模型采用的是交叉熵，通俗点理解交叉熵 推荐一篇文章讲的很清楚： 因此，交叉熵越低，这个策略就越好，最低的交叉熵也就是使用了真实分布所计算出来的信息熵，因…

    Linux 2023年6月6日
    086

  • Web开发静态资源处理

    Web开发静态资源处理 7.1 静态资源处理 我们要引入前端资源，项目中有许多的静态资源，比如css，js等文件，这个SpringBoot是怎么处理呢？ 如果我们是一个web应用，…

    Linux 2023年6月14日
    0118

  • redis订阅关闭异常解决

    redis订阅关闭异常解决 应用程序模块订阅redis运行一段时间出现一直重连Redis服务，日志如下： 2019-04-28 10:06:17,551 ERROR org.spr…

    Linux 2023年5月28日
    0115

  • Oracle中row_number()、rank()、dense_rank() 的区别

    row_number的用途非常广泛，排序最好用它，它会为查询出来的每一行记录生成一个序号，依次排序且不会重复，注意使用row_number函数时必须要用over子句选择对某一列进行…

    Linux 2023年6月14日
    0101

  • 【Example】C++ 接口概念讲解及例子演示

    C++ 和 Java 不同的是，C++ 没有 interface 关键字。对于很多新手来说，C++ 当中接口的概念不容易像 Java 当中那样被理解。 然而接口是面向对象编程当中的…

    Linux 2023年6月13日
    096

  • 【总结】瞬时高并发（秒杀/活动）Redis方案

    1，Redis 丰富的数据结构（Data Structures） * 字符串（String） – Redis字符串能包含 任意类型的数据 一个字符串类型的值最多能存储 …

    Linux 2023年5月28日
    091

  • Go实现安全双检锁的方法和最佳实践

    不安全的双检锁 从其他语言转入Go语言的同学经常会陷入一个思考：如何创建一个单例？ 有些同学可能会把其它语言中的双检锁模式移植过来，双检锁模式也称为懒汉模式，首次用到的时候才创建实…

    Linux 2023年6月13日
    0100

  • 利用Tensorboard可视化模型、数据和训练过程

    在60分钟闪电战中，我们像你展示了如何加载数据，通过为我们定义的 nn.Module的子类的model提供数据，在训练集上训练模型，在测试集上测试模型。为了了解发生了什么，我们在模…

    Linux 2023年6月14日
    0113

  • Kafka 配置文件详情

    kafka的配置分为 broker、producter、consumer三个不同的配置 一 、BROKER 的全局配置 最为核心的三个配置 broker.id、log.dir、zo…

    Linux 2023年6月8日
    091

  • TCP传输层协议 特性

    客户A和服务器B都处于建立连接的状态，此时客户A主动与服务器B发出断开连接的请求： 第一步：客户A会发送一个序号为Seq=u的报文给服务器B，此时控制位中的断开位FIN=1，即请求…

    Linux 2023年6月6日
    092

  • 测试计划

    ​ 1．测试计划的定义:描述需要完成的所有工作，包括被测项目的目的、背景、范围、资源、进度、环境、任务、策略，以及相应的风险和措施。 ​ 2.测试计划的作用: 对后面的测试过程起到…

    Linux 2023年6月7日
    079

  • Ubuntu 忘记登录密码

    重启Ubuntu，随即长按Shift（单系统）进入Grub菜单 选择Ubuntu高级选项 选择recovery mode进入Recovery Menu界面，选择Drop to ro…

    Linux 2023年6月16日
    0204

  • 基本数据类型的长度

    32位机器和64位机器中int、char等数据类型所占字节长度对比。 在32位机器和64机器中int类型都占用4个字节。编译器可以根据自身硬件来选择合适的大小，但是需要满足约束：s…

    Linux 2023年6月13日
    097

  • 用powershell实现，管理github自动化

    用powershell实现，管理github自动化 搜索关键字如下：PowerShellForGitHub powershell 传教士 原创文章。始于 2021-02-04 允许…

    Linux 2023年6月14日
    088
亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球