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