|
|
back to boardWhat's wrong with this problem? I always get WA even when I tried some of the solutions offered in the forum My solution is : #include <stdio.h> #define MAX 205 #define INF 2000000000 int n,m; int nasl[MAX][MAX]; int brn[MAX]; int vis[MAX]; int par[MAX]; int tree[MAX][MAX]; //short used[MAX][MAX]; int matr[MAX][MAX]; int brc; //short cycles[MAX*MAX][3]; // nachalo, kraj, naj-malko izpolzvanoto rebro int from,toFind; int count; int bri,bri2; int li[MAX*MAX],li2[MAX*MAX]; void DFS(int num) { int i; vis[num] = 1; for(i=0;i<brn[num];i++) { if(!vis[nasl[num][i]]) { tree[num][nasl[num][i]] = 1; tree[nasl[num][i]][num] = 1; par[nasl[num][i]] = num; DFS(nasl[num][i]); } } } void DFSW() { int i; for(i=0;i<n;i++) if(!vis[i]) { par[i] = -1; DFS(i); } } int main() { int i,i2,i3,cur; int a1,a2; // freopen("1077.in","r",stdin); scanf("%d %d",&n,&m); for(i=0;i<=n;i++) { vis[i] = 0; brn[i] = 0; for(i2=0;i2<n;i2++) { tree[i][i2] = 0; } } for(i=0;i<m;i++) { scanf("%d %d",&a1,&a2); nasl[a1-1][brn[a1-1]++] = a2-1; nasl[a2-1][brn[a2-1]++] = a1-1; matr[a1-1][a2-1] = matr[a2-1][a1-1] = 1; } DFSW(); // DFS(0); count = 0; for(i=0;i<n;i++) for(i2=i+1;i2<n;i2++) if(matr[i][i2]==1 && tree[i][i2]==0) count++; printf("%d\n",count); for(i=0;i<n;i++) for(i2=i+1;i2<n;i2++) if(matr[i][i2]==1 && tree[i][i2]==0) { bri = 0; bri2 = 0; cur = i; while(cur!=-1) { li[bri++] = cur; cur = par[cur]; } cur = i2; while(cur!=-1) { li2[bri2++] = cur; cur = par[cur]; } bri--; bri2--; while(li[bri]==li2[bri2]) { bri--; bri2--; } printf("%d ",bri+2+bri2+1); for(i3=0;i3<=bri+1;i3++) printf("%d ",li[i3]+1); for(i3=bri2;i3>=0;i3--) printf("%d ",li2[i3]+1); printf("\n"); } return 0; } |
|
|