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

用并查集,相当水,一次AC

Posted by loveqinqin at 2011-04-08 21:28:04 on Problem 1164
#include<stdio.h>
int set[2501],num[2501],map[51][51];
void init(int x)
{
	set[x]=x;
	num[x]=1;
}
int find(int x)
{
	if(set[x]==x)return x;
	return set[x]=find(set[x]);
}
void _union(int a,int b)
{
	int x1=find(a);
	int x2=find(b);
	if(x1==x2)
		return;
	if(num[x1]>num[x2])
	{
		set[x2]=x1;
		num[x1]+=num[x2];
	}
	else
	{
		set[x1]=x2;
		num[x2]+=num[x1];
	}
}

int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	int i,j,dir;
	for(i=0;i<n*m;i++)init(i);
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
		{
			scanf("%d",&dir);
			if(dir%2==0&&j>0)
				_union(i*n+j,i*n+j-1);
			if((dir>>1)%2==0&&i>0)
				_union(i*n+j,(i-1)*n+j);
			if((dir>>2)%2==0&&j<n-1)
				_union(i*n+j,i*n+j+1);
			if((dir>>3)%2==0&&i<m-1)
				_union(i*n+j,(i+1)*n+j);
		}
	int cnt=1,max=num[find(0)];
	for(i=1;i<m*n;i++)
	{
		int a1=find(i),a2=find(i-1);
		if(a1!=a2)
		{
			cnt++;
			if(num[a1]>max)
				max=num[a1];
			_union(a1,a2);
		}
	}
		printf("%d\n%d\n",cnt,max);
		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