|
|
back to boardCan anyone help me or give me some tests? Posted by train 30 Oct 2002 12:14 I think my method is right, but it always gets WR! Thank u! #include "stdio.h" int n, m, M[201][201]; int B[201][2], F[201]; void Init() { int i, j, k;
scanf("%d %d",&n,&m); for (i=1; i<=n; i++) for (j=1; j<=n; j++) M[i][j] = 0; for (k=0; k<m; k++) { scanf("%d %d",&i,&j); if (i!=j) M[i][j] = M[j][i] = 1; } } void CT(int num, int father, int level) { int i; F[num] = 1; B[num][0] = father; B[num][1] = level; for (i=1; i<=n; i++) if (!F[i] && M[num][i]) { M[num][i] = M[i][num] = 0; CT(i, num, level+1); } } void CreateTree() { int i;
for (i=1; i<=n; i++) F[i] = 0; /* for (i=1; i<=n; i++) if (!F[i]) { Pth[0] = i; nail = head = 0; B[i][0] = 0; B[i][1] = 1; F[i] = 1; while (head<=nail) { j = Pth[head]; head++; for (k=1; k<=n; k++) if (!F[k] && M[j][k]) { nail++; Pth[nail] = k; B[k][0] = j; B[k][1] = B[j][1] + 1; F[k] = 1; M[j][k] = M[k][j] = 0; } } }*/ for (i=1; i<=n; i++) { if (!F[i]) CT(i, 0, 1); } /* for (i=1; i<=n; i++) printf("%d %d\n",B[i][0],B[i][1]);*/ } void Caculate() { int total, i, j; int Pth[2][201], l[2]; for (i=1, total=0; i<=n; i++) for (j=1; j<=n; j++) if (M[i][j]==1) { total++; M[i][j] = M[j][i] = 2; } printf("%d\n",total); for (i=1; i<=n; i++) for (j=1; j<=n; j++) if (M[i][j]==2) { M[i][j] = M[j][i] = 0; l[0] = l[1] = 0; Pth[0][0] = i; Pth[1][0] = j;
while (Pth[0][l[0]]!=Pth[1][l[1]]) if (B[Pth[0][l[0]]][1]==B[Pth [1][l[1]]][1]) { l[0]++; Pth[0][l[0]] = B[Pth[0][l[0]-1]][0]; l[1]++; Pth[1][l[1]] = B[Pth[1][l[1]-1]][0]; } else if (B[Pth[0][l[0]]][1]>B [Pth[1][l[1]]][1]) { l[0]++; Pth[0][l[0]] = B[Pth[0][l[0]-1]][0]; } else { l[1]++; Pth[1][l[1]] = B[Pth[1][l[1]-1]][0]; } printf("%d",l[0]+l[1]+1); for (i=0; i<=l[0]; i++) printf(" % d",Pth[0][i]); for (i=l[1]-1; i>=0; i--) printf(" % d",Pth[1][i]); printf("\n"); } } main() { Init(); CreateTree(); Caculate(); } |
|
|