当前位置:首页 > 资讯 > info6 > 正文

zoj 1789 The Suspects

发表于: 2014-04-13   作者:chen_xinjia   来源:转载   浏览:
摘要: 好高兴,又AC一道,不过是很类似的两道。。还是好高兴呀思想跟2833是一样的,不过要重新设计输入和输出。老师上课又重新讲解了一下,因为嫌疑人已知是0,所以加入集中时应该默认让数值小的做树根,即最终让零做树根,这样子,只改了一点点,最后只要直接输出树根为零的树的大小就可以了。。。。。。。。。。。。。只是改良了一点点,但思想非常重要。。下面的程序仍然还是没有改的。。太懒了。。==// // //#i

好高兴,又AC一道 ,不过是很类似的两道。。还是好高兴呀思想跟2833是一样的,不过要重新设计输入和输出。老师上课又重新讲解了一下,因为嫌疑人已知是0,所以加入集中时应该默认让数值小的做树根,即最终让零做树根,这样子,只改了一点点,最后只要直接输出树根为零的树 的大小就可以了。。。。。。。。。。。。。只是改良了一点点,但思想非常重要。。下面的程序仍然还是没有改的。。太懒了。。= =

// 
//

//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include"memory.h"
using namespace std;
#define Maxsize 30000
int parent[Maxsize];
void WeightedUnion(int i, int j)
{
	//基于权重对根合并,将结点少的合并到结点多的
	int temp = parent[i] + parent[j];
	if (parent[j] < parent[i])//i的结点比较少
	{
		parent[i] = j;//i 成为j的结点
		parent[j] = temp;//j 的结点等于 i+j 
	}
	else//i的结点多于或等于j 的结点
	{
		parent[j] = i;
		parent[i] = temp;
	}
}
int findparent(int i)
{
	while (parent[i] >= 0)//不为根
	{
		i = parent[i];
	}
	return i;
}
int main( )
{

	int n, m, k, x, y;

	while (scanf("%d%d", &n, &m) != EOF)//n人m个社团
	{
		if (n == 0 && m == 0) break;//结束
		memset(parent, -1, sizeof(parent));//将每个根置为-1
		while (m--)
		{
			scanf("%d", &k);
			scanf("%d", &x);//先输入一个成员
			if (k == 1)
				continue;	//如果只有1成员,即没有朋友,没有合并的需要
		
			while (--k)
			{
				scanf("%d", &y);
				x = findparent(x);//找到自己所在的根
				y = findparent(y);
				if (x != y)//不是同一个根,不为同一个group
				{
					WeightedUnion(x, y);
				}
				x = y;
			}
		}
		printf("%d\n", -parent[findparent(0)]);
	}
	return 0;
}

1789

zoj 1789 The Suspects

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号