| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
49320K 2750MS,用短整型才不会超内存呀,怎么会这样?#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator