题目在这里

关于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 ;
}
 

最新文章

  1. Gradle&#39;s dependency cache may be corrupt解决方法
  2. 【004: gcc 和 clang 的简单比较】
  3. 【BZOJ 1178】【APIO 2009】CONVENTION会议中心
  4. java中的类型比较
  5. 解读 Windows Azure 存储服务的账单 – 带宽、事务数量,以及容量
  6. 将 Sublime 3 打造成 Python/Django IDE
  7. oracle删除表的方法
  8. java将Excel文件(xlsx,xls)转换为csv文件
  9. canvas 渐变
  10. UGUI实现的虚拟摇杆,可改变摇杆位置
  11. 1381: Munching(BFS)
  12. 3553: [Shoi2014]三叉神经树(树链剖分)
  13. cassandra简单介绍与基本操作
  14. Java学习笔记(一)网格袋布局
  15. Canvas中绘制贝塞尔曲线
  16. Oracle 中 编写 function 和 procedure 的注意事项
  17. 使用VB6读取数据库资源并发送邮件(原创)
  18. Pandas 处理丢失数据
  19. 实现一个简单的ConnectionPool
  20. python pyenv

热门文章

  1. 网格布局 GridLayout
  2. 【转载】 卷积神经网络(Convolutional Neural Network,CNN)
  3. 1. Tomcat之startup.sh
  4. o2s【我】
  5. 【PHP】php7.2报错The each() function is deprecated. This message will be suppressed on furthe
  6. DECODE函数和CASE WHEN 比较
  7. Django架站的16堂課
  8. xray写POC踩坑
  9. 【GStreamer开发】GStreamer基础教程02——GStreamer概念
  10. windows下安装JDK1.8和eclipse