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

49320K 2750MS,用短整型才不会超内存呀,怎么会这样?

Posted by tiaoer at 2012-08-19 16:31:47 on Problem 2553
#include<stdio.h>
#include<string.h>
short int array[5005][5005],zhan[5005],top,number,f[5005],zui[5005],color[5005];
short int sum_chudu[5005];
int n;
void dfs2(int u)
{
	int v;
	f[u]=number;
    color[u]=1;
	for(v=1;v<=n;v++)
	{
		if(array[u][v]==1&&color[v]==0)
		{
		
			dfs2(v);
		}
	}
	
	return ;
}
void dfs(int u)
{
	int v;
    color[u]=1;
	for(v=1;v<=n;v++)
	{
		if(array[u][v]==1&&color[v]==0)
		{
			dfs(v);
		}
	}
	zhan[top]=u;
	top++;
	return ;
}
int main()
{
	int i,j,u,v,e,x,y,w;
	for(;;)
	{
		memset(array,0,sizeof(array));
		scanf("%d",&n);
        if(n==0)  break;
		scanf("%d",&e);
		for(i=1;i<=e;i++)
		{
			scanf("%d%d",&x,&y);
			array[x][y]=1;
		}
        memset(color,0,sizeof(color));
		top=0;
		for(i=1;i<=n;i++)
		{
			if(color[i]==0)
			{
				dfs(i);
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=i;j<=n;j++)
			{
				w=array[i][j];
				array[i][j]=array[j][i];
				array[j][i]=w;
			}
		}
		number=0;//强联通分量的个数
		memset(color,0,sizeof(color));
		for(i=top-1;i>=0;i--)
		{
			if(color[zhan[i]]==0)
			{
				number++;
				dfs2(zhan[i]);
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=i;j<=n;j++)
			{
				w=array[i][j];
				array[i][j]=array[j][i];
				array[j][i]=w;
			}
		}
		if(number==1)
		{
			for(i=1;i<=n;i++)
			{
				printf("%d ",i);
			}
			printf("\n");
			continue;
		}
		//printf("%d\n",number);
		for(i=1;i<=number;i++)
		{
			sum_chudu[i]=0;
			for(u=1;u<=n;u++)
			{
				if(f[u]==i)
				{
					for(v=1;v<=n;v++)
					{
						if(array[u][v]==1&&f[v]!=i)
						{
						   sum_chudu[i]++;
						}
					}
				}
			}
		}
		memset(zui,0,sizeof(zui));
		for(i=1;i<=number;i++)
		{
			if(sum_chudu[i]==0)
			{
				for(u=1;u<=n;u++)
				{
					if(f[u]==i)
					{
						zui[u]=1;
					}
				}
			}
		}
		for(i=1;i<=5004;i++)
		{
			if(zui[i]==1)
			{
				printf("%d ",i);
			}
		}
		printf("\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