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

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

Posted by DaiPeng_JNU at 2017-04-21 17:10:06 on Problem 1703
In Reply To:哪位仁兄指点指点wa了好久了 , 都检查不出来!!!!!!!!!! Posted by:sw1001 at 2011-04-01 20:47:37
> #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