POJ1611(The Suspects)--简单并查集
2024-08-27 05:50:09
关于SARS病毒传染的问题。在同一个组的学生是接触很近的,后面也会有新的同学的加入。其中有一位同学感染SARS,那么该组的所有同学得了SARS。要计算出有多少位学生感染SARS了。编号为0的同学是得了SARS的。
直接用并查集解决水掉
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
#define MAX 100 struct node
{
int no;//编号
int rank;
int parent;
int total;
}; class DisJoinSet
{
protected:
int n;
node * tree;
public:
DisJoinSet(int n );
~DisJoinSet();
void Init();
void Union(int x,int y);
int Find(int x);
int GetAswer(int x);
}; DisJoinSet ::DisJoinSet(int n)//初始化操作
{
this->n = n;
tree = new node[n];
for(int i = ; i < n; i++)
{
tree[i].no = i;
tree[i].parent = i;
tree[i].total = ;
tree[i].rank = ;
}
}
DisJoinSet::~DisJoinSet()
{
delete[] tree;
} void DisJoinSet :: Init()
{
}
int DisJoinSet::Find(int x)
{
int temp = tree[x].parent;//temp 为x的父亲结点
if( x != tree[x].parent)
{
tree[x].parent = Find(tree[x].parent);//路径压缩
return tree[x].parent;
}
else
{
return x;
}
} void DisJoinSet ::Union(int x,int y)
{
int rootx = Find(x);
int rooty = Find(y);
if(rootx == rooty)
{
return ;
}
else//并查集基本操作
{
if(tree[rootx].rank < tree[rooty].rank)
{
tree[rootx].parent = rooty;
tree[rooty].total += tree[rootx].total;
}
else
{
tree[rooty].parent = rootx;
tree[rootx].total += tree[rooty].total;
if(tree[rootx].rank == tree[rooty].rank)
{
tree[rootx].rank++;
}
}
}
} int DisJoinSet::GetAswer(int x)//返回xtotal
{
int t = Find(x);
return tree[t].total;
} int main()
{
int n;
int m;
while(cin>>n>>m && n!= && m>= )
{
DisJoinSet dis(n);
int per1;
int per2;
for(int i = ; i< m;i++)
{
int num = ;
cin>>num;
cin>>per1;
for(int i = ;i < num; i++)
{
cin>>per2;
dis.Union(per1,per2);
}
}
cout<<dis.GetAswer()<<endl;
}
return ;
}
最新文章
- Gradle&#39;s dependency cache may be corrupt解决方法
- 【004: gcc 和 clang 的简单比较】
- 【BZOJ 1178】【APIO 2009】CONVENTION会议中心
- java中的类型比较
- 解读 Windows Azure 存储服务的账单 – 带宽、事务数量,以及容量
- 将 Sublime 3 打造成 Python/Django IDE
- oracle删除表的方法
- java将Excel文件(xlsx,xls)转换为csv文件
- canvas 渐变
- UGUI实现的虚拟摇杆,可改变摇杆位置
- 1381: Munching(BFS)
- 3553: [Shoi2014]三叉神经树(树链剖分)
- cassandra简单介绍与基本操作
- Java学习笔记(一)网格袋布局
- Canvas中绘制贝塞尔曲线
- Oracle 中 编写 function 和 procedure 的注意事项
- 使用VB6读取数据库资源并发送邮件(原创)
- Pandas 处理丢失数据
- 实现一个简单的ConnectionPool
- python pyenv
热门文章
- 网格布局 GridLayout
- 【转载】 卷积神经网络(Convolutional Neural Network,CNN)
- 1. Tomcat之startup.sh
- o2s【我】
- 【PHP】php7.2报错The each() function is deprecated. This message will be suppressed on furthe
- DECODE函数和CASE WHEN 比较
- Django架站的16堂課
- xray写POC踩坑
- 【GStreamer开发】GStreamer基础教程02——GStreamer概念
- windows下安装JDK1.8和eclipse