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 HH_YT at 2012-08-12 10:22:29 on Problem 3207
#include<stdio.h>
#include<string.h>
int n,m;
int node[1001][1001];
int wire[501][2];
int index;
int cnt;
int stack[1001];
int snum;
int instack[1001];
int belong[1001];
int low[1001];
int DFN[1001];
int tarjan(int n)
{
	stack[++snum]=n;
	instack[n]=1;
	low[n]=DFN[n]=++index;
	for(int i=1;i<=node[n][0];i++)
	{
		if(!DFN[node[n][i]])
		{
			tarjan(node[n][i]);
			if(low[node[n][i]]<low[n])
				low[n]=low[node[n][i]];
		}
		else if(instack[node[n][i]]&&DFN[node[n][i]]<low[n])
		{
			low[n]=DFN[node[n][i]];
		}
	}
	if(low[n]==DFN[n])
	{
		cnt++;
		while(stack[snum]!=n)
		{
			belong[stack[snum]]=cnt;
			snum--;
		}
		belong[n]=cnt;
		snum--;
	}
	return 0;
}
int main()
{
	int i,j;
	int a,b;
	int z;
	int sum;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=2*m;i++)
			node[i][0]=0;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&wire[i][0],&wire[i][1]);
		}
		for(i=1;i<=m;i++)
			for(j=i+1;j<=m;j++)
			{
				if(wire[i][0]>wire[i][1])
				{
					a=wire[i][1];
					b=wire[i][0];
				}
				else
				{
					a=wire[i][0];
					b=wire[i][1];
				}
				sum=0;
				for(z=0;z<=1;z++)
				{
					if(wire[j][z]>a&&wire[j][z]<b)
						sum++;
				}
				if(sum==1)
				{
					node[i][++node[i][0]]=j+m;
					node[i+m][++node[i+m][0]]=j;
					node[j][++node[j][0]]=i+m;
					node[j+m][++node[j+m][0]]=i;
				}
			}
			memset(DFN+1,0,sizeof(int)*m*2);
			cnt=0;
			index=0;
			snum=0;
			memset(instack,0,sizeof(instack));
			for(i=1;i<=2*m;i++)
			{
				if(!DFN[i])
					tarjan(i);
			}
			int flag=0;
			for(i=1;i<=m;i++)
			{
				if(belong[i]==belong[i+m])
				{
					flag=1;
					break;
				}
			}
			if(flag)
				printf("the evil panda is lying again\n");
			else
				printf("panda is telling the truth...\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