概述
文章作者：ktyanny 文章来源：ktyanny 转载请注明，谢谢合作。
ktyanny：a的第一道并查集。
题目描述：
有很多组学生，在同一个组的学生经常会接触，也会有新的同学的加入。但是SARS是很容易传染的，只要在改组有一位同学感染SARS，那么该组的所有同学都被认为得了SARS。现在的任务是计算出有多少位学生感染SARS了。假定编号为0的同学是得了SARS的。
解题思路---->显然并查集了。并查集的详细解释在可以点击 并查集（不相交集合）进行学习。采用num[]存储该集合中元素个数，并在集合合并时更新num[]即可。然后找出0所在的集合的根节点x，因此，num[x]就是answer了。
ac代码： 16MS C++
#include
<
stdio.h
>
//by ktyanny
#include < iostream >
using namespace std;
const int MAXN = 30001 ; /* 结点数目上线 */
int pa[MAXN]; /* p[x]表示x的父节点 */
int rank[MAXN]; /* rank[x]是x的高度的一个上界 */
int num[MAXN]; /* num[]存储该集合中元素个数，并在集合合并时更新num[]即可 */
void make_set( int x)
{ /* 创建一个单元集 */
pa[x] = x;
rank[x] = 0 ;
num[x] = 1 ;
}
int find_set( int x)
{ /* 带路径压缩的查找 */
/* 保存待查找的数 */
int r = x, temp;
/* 找到根节点 */
while (pa[r] != r) r = pa[r];
while (x != r)
{
temp = pa[x];
pa[x] = r;
x = temp;
}
return x;
// if(x != pa[x]) //注释掉的其实也是可以的，不过不想用递归来做啦
// pa[x] = find_set(pa[x]);
// return pa[x];
}
/* 按秩合并x，y所在的集合 */
void union_set( int x, int y)
{
x = find_set(x);
y = find_set(y);
if (x == y) return ;
if (rank[x] > rank[y]) /* 让rank比较高的作为父结点 */
{
pa[y] = x;
num[x] += num[y];
}
else
{
pa[x] = y;
if (rank[x] == rank[y])
rank[y] ++ ;
num[y] += num[x];
}
}
// answer to 1611
int main()
{
int n, m, x, y, i, t, j;
while (scanf( " %d%d " , & n, & m))
{
if (m == n && n == 0 ) break ;
if (m == 0 )
{
cout << " 1n " ; continue ;
}
for (i = 0 ; i < n; i ++ )
make_set(i);
for (i = 0 ; i < m; i ++ )
{
scanf( " %d " , & t);
scanf( " %d " , & x);
for (j = 1 ; j < t; j ++ ){
scanf( " %d " , & y);
union_set(x, y);
x = y;
}
}
x = find_set( 0 ); /* 找到0所在的树的树根 */
// int ans = 0;
// for(i = 0; i < n; i++)
// if(pa[i] == x)
// ans++;
// cout << ans << endl;
cout << num[x] << endl;
}
return 0 ;
}
#include < iostream >
using namespace std;
const int MAXN = 30001 ; /* 结点数目上线 */
int pa[MAXN]; /* p[x]表示x的父节点 */
int rank[MAXN]; /* rank[x]是x的高度的一个上界 */
int num[MAXN]; /* num[]存储该集合中元素个数，并在集合合并时更新num[]即可 */
void make_set( int x)
{ /* 创建一个单元集 */
pa[x] = x;
rank[x] = 0 ;
num[x] = 1 ;
}
int find_set( int x)
{ /* 带路径压缩的查找 */
/* 保存待查找的数 */
int r = x, temp;
/* 找到根节点 */
while (pa[r] != r) r = pa[r];
while (x != r)
{
temp = pa[x];
pa[x] = r;
x = temp;
}
return x;
// if(x != pa[x]) //注释掉的其实也是可以的，不过不想用递归来做啦
// pa[x] = find_set(pa[x]);
// return pa[x];
}
/* 按秩合并x，y所在的集合 */
void union_set( int x, int y)
{
x = find_set(x);
y = find_set(y);
if (x == y) return ;
if (rank[x] > rank[y]) /* 让rank比较高的作为父结点 */
{
pa[y] = x;
num[x] += num[y];
}
else
{
pa[x] = y;
if (rank[x] == rank[y])
rank[y] ++ ;
num[y] += num[x];
}
}
// answer to 1611
int main()
{
int n, m, x, y, i, t, j;
while (scanf( " %d%d " , & n, & m))
{
if (m == n && n == 0 ) break ;
if (m == 0 )
{
cout << " 1n " ; continue ;
}
for (i = 0 ; i < n; i ++ )
make_set(i);
for (i = 0 ; i < m; i ++ )
{
scanf( " %d " , & t);
scanf( " %d " , & x);
for (j = 1 ; j < t; j ++ ){
scanf( " %d " , & y);
union_set(x, y);
x = y;
}
}
x = find_set( 0 ); /* 找到0所在的树的树根 */
// int ans = 0;
// for(i = 0; i < n; i++)
// if(pa[i] == x)
// ans++;
// cout << ans << endl;
cout << num[x] << endl;
}
return 0 ;
}
测试数据：
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
转载于:https://www.cnblogs.com/ktyanny/archive/2009/12/09/1620304.html
最后
以上就是儒雅枫叶为你收集整理的POJ 1611 The Suspects （并查集）的全部内容，希望文章能够帮你解决POJ 1611 The Suspects （并查集）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复