B - The Suspects(并查集)
2024-09-04 13:26:06
B - The Suspects
Time Limit:1000MS Memory Limit:20000KB 64bit IO Format:%lld & %llu
Description
严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会, 最好的策略是隔离可能的患者。
在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。为了防止非典的传播,NSYSU收集了所有学生团体的成员名单。他们的标准操作程序(SOP)如下:
一旦一组中有一个可能的患者, 组内的所有成员就都是可能的患者。
然而,他们发现当一个学生被确认为可能的患者后不容易识别所有可能的患者。你的工作是编写一个程序, 发现所有可能的患者。
Input
输入文件包含多组数据。
对于每组测试数据:
第一行为两个整数n和m, 其中n是学生的数量, m是团体的数量。0 < n <= 30000,0 <= m <= 500。
每个学生编号是一个0到n-1之间的整数,一开始只有0号学生被视为可能的患者。
紧随其后的是团体的成员列表,每组一行。
每一行有一个整数k,代表成员数量。之后,有k个整数代表这个群体的学生。一行中的所有整数由至少一个空格隔开。
n = m = 0表示输入结束,不需要处理。
Output
对于每组测试数据, 输出一行可能的患者。
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1 //初学并查集,第二周训练第一个完全没百度做出来的,中规中矩的,虽然过了但是用了 352KB 922ms,好险。以后有机会更新优化。
#include <iostream>
#include <cstdio>
using namespace std; const int N=;
int set_tree[N];
int person[N];
bool flag[N]; void Init ()
{
for (int i=;i<N;i++)
{
set_tree[i]=i;
flag[i]=;
}
} int find_head(int x)
{
while (x!=set_tree[x]) x=set_tree[x];
return x;
} void link(int x,int y)
{
x=find_head(x);
y=find_head(y);
if (x==y) return;
set_tree[x]=set_tree[y];
} void hebing(int p)
{
int i;
for (i=;i<p-;i++)//合并p个人.0.1,1.2,......,p-2.p-1 合并
{
link(person[i],person[i+]);
}
} int main()
{
int n,m,p,i,all;
Init();
while (scanf("%d%d",&n,&m))
{
if (n==&&m==) break;
Init();
all=;
while (m--)
{
scanf("%d",&p);
for (i=;i<p;i++)
{
scanf("%d",&person[i]);
flag[person[i]]=;
}
hebing(p);
} for (i=;i<n;i++)
{
if (flag[i]==&&find_head(i)==find_head())
all++;
}
printf("%d\n",all); }
return ;
}
//原来要路径压缩 468k 16ms
#include <iostream>
#include <cstdio>
using namespace std; const int N=;
int f[N];
int person[N];
bool flag[N]; void Init ()
{
for (int i=;i<N;i++)
{
f[i]=i;//并查集初始化
flag[i]=;
}
} int find_head(int x)
{
if (x!=f[x])
f[x]=find_head(f[x]);
return f[x];
} void link(int x,int y)
{
x=find_head(x);
y=find_head(y);
if (x==y) return;
f[x]=f[y];
} int main()
{
int n,m,p,i,j,all;
Init();
while (scanf("%d%d",&n,&m))
{
if (n==&&m==) break;
Init(); all=;// 一开始 0 号就是患者 while (m--)
{
scanf("%d",&p);
for (i=;i<p;i++)
{
scanf("%d",&person[i]);
flag[person[i]]=;
}
for (j=;j<p-;j++)//合并p个人.0.1,1.2,......,p-2.p-1 合并
link(person[j],person[j+]);
} for (i=;i<n;i++)
{
if (flag[i]==&&find_head(i)==find_head())
all++;
}
printf("%d\n",all); }
return ;
}
最新文章
- 修复bootstrap daterangepicker中的3个问题
- 电子现金、电子钱包、qPBOC、闪付、UPCash
- Ambari是什么?
- 一、Struts2的概述
- 了解Unix进程(1)
- 【Android车载系统 News | Tech 2】News 谷歌开发新车载系统!安卓Auto不是终点 2014-12-20
- Unity3D脚本中文系列教程(六)
- 嵌入式 Linux 应用:概述
- Objective-C /iphone开发基础:协议(protocol)
- 【Tika基础教程之一】Tika基础教程
- struts2和struts1认识
- sqlDeveloper连接oracle
- Sublime Text3介绍和插件安装——基于Python开发
- guava 学习笔记 瓜娃(guava)的API快速熟悉使用
- Codeforces Round #504 D. Array Restoration
- Bunder: What does :require =>; nil in Gemfile mean?
- Django中模型(四)
- Virtual Treeview 安装以及入门
- 《ArcGIS Runtime SDK for Android开发笔记》——(5)、基于Android Studio构建ArcGIS Android开发环境(离线部署)(转)
- 5.3类集(java学习笔记)集合的输出