當前位置:首頁 > 資訊 > 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號
广东25选5开奖结果