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

POJ1611(The Suspects)–简单并查集

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

大家都在看

  • CentOS7.6下Oracle19C RAC集群詳細搭建步驟

    CentOS7.6搭建RAC 1.系统环境配置 1.1概述 ​ 搭建两个节点的rac集群，其每个节点均有两个网卡，public网卡和private网卡。两个节点的主机名分别为rac…

    Linux 2023年6月13日
    078

  • 用Markdown写Html和.md也就图一乐，真骚操作还得用来做PPT

    前言 和这篇文章一样，我就是用Markdown写的。相信各位平时也就用Markdown写写文档，做做笔记，转成XHtml、Html等，今天教大伙一招骚操作：用Markdown写PP…

    Linux 2023年6月13日
    0120

  • SQL实战——04. 查找所有已经分配部门的员工的last_name和first_name以及dept_no （一个逗号引发的血案）

    查找所有已经分配部门的员工的last_name和first_name以及dept_noCREATE TABLE dept_emp (emp_no int(11) NOT NULL,…

    Linux 2023年6月14日
    090

  • WebBug Java漏洞靶场 Java代码审计

    404. 抱歉，您访问的资源不存在。 可能是网址有误，或者对应的内容被删除，或者处于私有状态。 代码改变世界，联系邮箱 contact@cnblogs.com 园子的商业化努力-困…

    Linux 2023年6月6日
    0107

  • Linux服务器配置git服务

    现在 Github 已经支持个人建立私有仓库，包括国内的一些开源平台如 Gitee 等也支持私有仓库，所以直接去建立私有仓库即可。或者可以自己买服务器搭建 GitLab。但是这篇文…

    Linux 2023年6月14日
    0112

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

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

    Linux 2023年6月13日
    0122

  • linux_arch

    由于以前新手开始接触的是ubuntu，然后通过ubuntu又开始了解centos,这俩系统基本是稳定版本可以用作服务器，但是centos的还是居多，一来比较接近redhat；但是这…

    Linux 2023年6月14日
    095

  • Ubuntu系统中防火墙的使用和开放端口

    sudo sudo apt-get install ufw sudo ufw status inactive: 不活跃，未开启 active:开启 sudo ufw enable …

    Linux 2023年5月27日
    094

  • Windows10公钥远程连接Linux服务器

    前言 一、环境准备 二、使用步骤 – 1.服务器安装并配置OpenSSH 2. 本地生成密钥 3. 服务器ssh添加密钥 三 总结 前言 使用公钥远程登陆Linux十分…

    Linux 2023年6月7日
    0103

  • mysql二进制安装脚本部署

    mysql二进制安装脚本部署 mysql二进制安装脚本部署 单实例 使用函数的单实例 使用函数的单实例或者多实例 单实例 [root@localhost ~]# mkdir mys…

    Linux 2023年6月6日
    0121

  • Redis 的 5 个常见使用场景

    在这篇文章中，我们将阐述 Redis 最常用的使用场景，以及那些影响我们选择的不同特性。 最常用的一种使用Redis的情景是会话缓存（session cache）。用Redis缓存…

    Linux 2023年5月28日
    0114

  • 高速USB转4串口产品设计-RS232串口

    基于480Mbps 高速USB转8路串口芯片CH344Q，可以为各类主机扩展出4个独立的串口。CH344芯片支持使用操作系统内置的CDC串口驱动，也支持使用厂商提供的VCP串口驱动…

    Linux 2023年6月7日
    0109

  • Linux基础学习（二）

    显示/etc目录下，以非字母开头，后面跟了一个字母以及其它任意长度任意字符的文件或目录 [root@ct7 ~]# ls /etc | grep -E “^[0-9][a-z]*”…

    Linux 2023年6月8日
    093

  • Linux errno

    Linux errno,number of last error. Linux/include/uapi/asm-generic/errno-base.h ifndef _ASM_…

    Linux 2023年6月7日
    0115

  • Shell文件属性的判断与比较

    Shell支持对文件属性的判断，常用的文件属性操作符很多，如下表所示。更多文件属性操作符可以参考命令帮助手册man test [root@centos7&#xFF5E;]#…

    Linux 2023年6月6日
    095

  • 关闭linux内核反向路由

    route -n Kernel IP routing tableDestination Gateway Genmask Flags Metric Ref Use Iface0.0….

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