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

POJ1611(The Suspects)–简单并查集

• Linux • 阅读 109 
  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语言 刷题答案下载！

大家都在看

  • 剑指offer计划28（搜索与回溯算法困难）—java

    1.1、题目1 剑指 Offer 37. 序列化二叉树 1.2、解法 这题给我笑死了，我看到题解有个解法，我愿称之为神。 public class Codec { private …

    Linux 2023年6月11日
    098

  • JAVA设计模式-适配器模式

    JAVA设计模式-适配器模式 介绍 适配器模式是一种结构型模式，它主要解决接口之间的兼容问题。当我们需要使用某个类的接口时，但是这个类的接口目前并不符合我们使用需求，不能直接使用，…

    Linux 2023年6月6日
    0102

  • k8安装

    1.安装k8s之前需要安装docker,etcd 因为要在k8s的pod中运行容器，需要先安装 容器运行时（Container Runtimes ） 几种常见的容器运行时与 Kub…

    Linux 2023年6月13日
    088

  • 意犹未尽的第2篇再次推出，继续讲解oracledb_exporter监控Oracle，一个入侵性极低的监控方案。

    写在开篇 基于上次的 oracledb_exporter监控Oracle，一个入侵性极低的监控方案 文章中，本篇继续讲解如下内容： 根据实际业务需求编写自定义监控指标，让其真正可以…

    Linux 2023年6月7日
    094

  • CentOS-7配置fastDFS文件服务器和安装Nginx

    配置步骤实在是很繁琐，听我慢慢道来！ 主要是配置管理（tracker）和存储（storage）返回地址样式 –> 域名/组名/磁盘名/目录名/文件名 &#8211…

    Linux 2023年6月13日
    090

  • RAID级别

    常用选项 模式： 创建：-C 装配：-A 监控：-F 管理：-f, -r, -a < raiddevice> : /dev/md# < component-dev…

    Linux 2023年6月6日
    086

  • 如何搭建android源代码repo仓库

    .版本： v0.3作者：河东西望日期：2022-7-5. 如果你的开发是基于AOSP源码来建仓，那么搭建repo服务器和部署自己的repo仓库就是非常必要的工作了。 现实中很多公司…

    Linux 2023年6月7日
    073

  • Redis 事务与锁

    基本操作 事务的基本操作 开启事务，设定事务的开启位置，此指令执行后，后续的所有指令均加入到事务中 multi 取消事务，终止当前事务的定义，发生在 multi 之后，exec 之…

    Linux 2023年5月28日
    076

  • macos 文件系统 git仓库 大小写敏感设置; git config core.ignorecase

    macos 的文件系统不区分文件名的大小写，这样会导致在一个文件夹，当修改一个文件名为大写的时候，git不能感知到。这样使用过程中会出现很多不必要的麻烦。之前设置过，最近使用，发现…

    Linux 2023年6月14日
    0110

  • Linux连接出现Permission denied (publickey,gssapi-with-mic,password

    新建的机器或者利旧的机器，当再次连接旧机器时出现以下报错： @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@…

    Linux 2023年6月13日
    070

  • 5.8 Vim多窗口编辑模式

    在编辑文件时，有时需要参考另一个文件，如果在两个文件之间进行切换则比较麻烦。可以使用 Vim 同时打开两个文件，每个文件分别占用一个窗口。 例如，在査看 /etc/passwd 时…

    Linux 2023年6月7日
    0165

  • JavaScript 做的网页版扫雷小游戏

    闲来无事做了个网页版扫雷小游戏，基本实现了扫雷客户端的全部功能。但是感觉面向对象用的还不是很好，有待优化。 游戏地址：http://twgdh.com/saolei/index.h…

    Linux 2023年6月13日
    0109

  • 2021年度总结 2022年度规划

    2021年 计划 1、学习更多的知识😁 2、学习408的知识，至少能熟悉计算机组成原理、操作系统、计算机网络、算法这几个的联系，区别等。😁 3、整理408的知识到博客上。 （一篇未…

    Linux 2023年6月13日
    089

  • 面试必问的安卓虚拟机，你真的掌握了么？——安卓虚拟机基础知识回顾

    前言 21世纪，安卓虚拟机正在一步步的走入我们的生活，小到个人部分朋友在电脑上使用安卓虚拟机玩手游，大到安卓从业人员在虚拟机上面跑程序。不得不承认，对于每一位Androider 而…

    Linux 2023年6月13日
    093

  • 简单易用的任务队列-beanstalkd

    概述 beanstalkd 是一个简单快速的分布式工作队列系统，协议基于 ASCII 编码运行在 TCP 上。其最初设计的目的是通过后台异步执行耗时任务的方式降低高容量 Web 应…

    Linux 2023年6月7日
    0100

  • 建表参数PCTFREE、PCTUSED、INITRANS和MAXTRANS释疑

    PCTFREE与PCTUSED建表时可以指定以上两个参数的值（整数），PCTFREE表示一个块中保留的剩余空间大小百分比，该保留空间主要用于已有记录的更 新操作；PCTUSED表示…

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