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 sw1001 at 2011-04-02 16:32:36 on Problem 2492
#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)
{
	int temp;
	if(x!=father[x])
	{
		temp=father[x];
		father[x]=findset(father[x]);
		kind[x]=(kind[x]+kind[temp])%2;

	}

	return father[x];


}


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

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

}

int main()
{

	int T, N , M, ai, bi, aai, bbi, kk, tt, tag;

	

	scanf("%d", &T);

	for(kk=0;kk<T;++kk)
	{
		scanf("%d%d", &N, &M);
		
		makeset(N);
		tag=0;

		for(tt=0;tt<M;++tt)
		{
			
			
			scanf("%d%d",&ai, &bi);

			
			
			aai=findset(ai);
			bbi=findset(bi);

			if(aai!=bbi)
			{
				Union(ai, bi);
			}
			else 
			{
				if(kind[bi]==kind[ai])
				{
					tag=1;
					
					
				}
			
			}
		}

		if(tag==0) 
		{
			printf("Scenario #%d:\n", kk+1);
			printf("No suspicious bugs found!\n\n");
		}
		else
		{
			printf("Scenario #%d:\n", kk+1);
			printf("Suspicious bugs found!\n\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