[Home|Training|Problems|Contests|C Language] | [Login|Register] |
New post Show post Search forum |
Read post
#include<stdio.h>
#include<stdlib.h> #include<string.h> int i,j,n,m,bs,a,b,ex,ans,maxn; int s[201][201],r[201],le[201],d[201],lj[50000],c[201][201]; struct { int a,b; }bi[50000]; void search() { int i,l=1,k,r1=1; d[1]=1; r[1]=1;le[1]=0; while (l<=r1) { k=d[l]; l++; for (i=1;i<=lj[k];i++) if (r[c[k][i]]==0 ) { r1++; d[r1]= c[k][i]; le[c[k][i]]=le[k]+1; r[c[k][i]]=1; bs++; bi[bs].a=k; bi[bs].b=d[r1]; } } } void search1() { int i,l=1,k,r1=1; d[1]=1; r[1]=1;le[1]=0; while (l<=r1) { k=d[l]; l++; for (i=1;i<=lj[k];i++) if (r[c[k][i]]!=1 && s[k][c[k][i]]==1) { r1++; d[r1]=c[k][i]; le[c[k][i]]=le[k]+1; r[c[k][i]]=1; } } } void main() { scanf("%d%d",&n,&m); while (n!=0 && m!=0) { memset(s,0,sizeof(int)*201*201); memset(r,0,sizeof(int)*201); memset(lj,0,sizeof(int)*201); bs=0; le[i]=1000; for (i=1;i<=n;i++) for (i=1;i<=m;i++) { scanf("%d%d",&a,&b); lj[a]++; lj[b]++; c[a][lj[a]]=b; c[b][lj[b]]=a; s[a][b]=1; s[b][a]=1; } ans=0; search(); for (j=1;j<=bs;j++) { memset(r,0,sizeof(int)*201); s[bi[j].a][bi[j].b]=0; ex=0; s[bi[j].b][bi[j].a]=0; maxn=0; for (i=1;i<=n;i++) le[i]=1000; le[1]=0; search1(); for (i=2;i<=n;i++) if (le[i]==1000) ex=1; else if (le[i]>maxn) maxn=le[i]; if (maxn>ans) ans=maxn; s[bi[j].a][bi[j].b]=1; s[bi[j].b][bi[j].a]=1; } if (ex==1) printf("Great\n"); else printf("%d\n",ans); scanf("%d%d",&n,&m); } } Reply
|