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
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

哪位仁兄指点指点wa了好久了 , 都检查不出来!!!!!!!!!!

Posted by sw1001 at 2011-04-01 20:47:37 on Problem 1703
#include <stdio.h>

int father[100010], kind[100010];


void makeset(int n)
{
	int i;

	for(i=1;i<=n;++i)
	{
		father[i]=i;

		kind[i]=0;

	}

}


int findset(int x)
{
	if(x!=father[x])
	{
		father[x]=findset(father[x]);
		kind[x]=(kind[x]+kind[father[x]])%2;

	}

	return father[x];

}


void Union(int x, int y)
{
	int xx, yy;
	xx=findset(x);
	yy=findset(y);

	if(xx==yy)
		return ;
	else
	{

		father[yy]=xx;
		kind[yy]=(kind[x]+kind[y]+1)%2;
	}

}

int main()
{

	int T, N , M, ai, bi, aai, bbi;

	char strc;

	scanf("%d", &T);

	while(T--)
	{
		scanf("%d%d", &N, &M);
		
		makeset(N);

		while(M--)
		{
			
			
			scanf("\n%c%d%d",&strc ,&ai, &bi);

			
			if(strc=='D')
			{
				Union(ai, bi);
				
			}
			else
			{
				aai=findset(ai);
				bbi=findset(bi);

				if(aai!=bbi)
				{
					printf("Not sure yet.\n");
				}
				else if(aai==bbi)
				{
					if(kind[bi]==kind[ai])
					{
						printf("In the same gang.\n");

					}
					else
					{
						printf("In different gangs.\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