Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

= =

Posted by xuhaoran510 at 2011-06-26 12:54:42 on Problem 1611
In Reply To:苍天呐!!为毛一直wa!!!! Posted by:ylqfp at 2011-06-26 11:09:34
直接在提交框里改的代码,没有缩进,抱歉>__<
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
#define N 300005
int parent[N], rank[N];

void this_init()
{
	memset(parent, -1, sizeof(parent));
	memset(rank, -1, sizeof(rank));
}

void make_set(int x)
{
	parent[x] = x;
	rank[x] = 1;
}

int find_set(int x)
{
	if (x != parent[x])
	{
		parent[x] = find_set(parent[x]);
	}
	return parent[x];
}


void link_set(int x, int y)
{

	if (rank[x] > rank[y])
	{
		parent[y] = x;
		rank[x] += rank[y];
	}
	else
	{
		parent[x] = y;
		rank[y] += rank[x];
	}
}

void union_set(int x, int y)
{
	link_set(find_set(x), find_set(y));
}


int main()
{
		int n,m,i,j,k;
		this_init();
		while (cin >> n >> m)
		{
			if (n==0 && m==0)
			{
				break;
			}
			for (i=0; i<n; i++)
			{
				make_set(i);
			}
			//cout<<"make set success\n";
			int group_num,first;
			for (i=0; i<m; i++)
			{
				cin>>group_num; if (!group_num) continue;
                                cin>>first;
				int a;
				for (j=1; j<group_num; j++)
				{
					cin >> a;
					union_set(a, first);
				//	cout<<"union"<<a<<" "<<first<<endl;
				}

			}
int px=find_set(0);
int ans=0; for (i=0; i<n; i++) if (find_set(i)==px) ans++;
cout<<ans<<"\n";

		}

		return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator