2042868 2006-08-25 18:19:49 Accepted 1141 C++ 00:00.40 408K St.Crux 2042840 2006-08-25 17:48:34 Accepted 1141 C++ 00:03.04 848K St.Crux 一个是c，一个是c++，一样的算法。这数据读取的效率差的真多。 这题还算个简单的题。用c写时，读取的时候比较麻烦。p[n][0]表示的是该点的父节点。p[n][1]表示的是该点的层次。 #include <cstdio>#include <string> int n, m, p[1001][2], ans[1001]; int cca(int a, int b){ while(p[a][1] > p[b][1]) {  a = p[a][0]; } while(p[b][1] > p[a][1]) {  b = p[b][0]; } while(p[a][1]) {  if(a == b)   break;  a = p[a][0], b = p[b][0]; } return a;} int main(){ //freopen("in.txt", "r", stdin); int i, j, x, y; char c; while(scanf ("%d", &n) == 1) {     memset(ans, 0, sizeof(ans));  memset(p, 0, sizeof(p));  for (i = 0; i < n; i ++)  {   scanf ("%d", &x);    scanf ("%c", &c);   scanf ("%c", &c);   m = 0;   while (1)   {    scanf ("%c",&c);    if (c >= '0' && c <= '9')      m = m * 10 + (int)c - 48;     else break;   }   scanf ("%c",&c);   for(j = 0; j < m; j ++)   {    scanf("%d", &y);     p[y][0] = x;      p[y][1] = p[x][1] + 1;   }      }      scanf ("%d\n", &m);  for (i = 0; i < m; i ++)  {   scanf ("%c", &c);   x = 0, y = 0;   while (1)   {    scanf ("%c", &c);    if ((c >= '0') && (c <= '9'))      x = x * 10 + (int)c - 48;     else break;   }   while (1)   {    scanf ("%c", &c);    if ((c >= '0') && (c <= '9'))      y = y * 10 + (int)c - 48;     else break;   }   scanf ("%c", &c);   //printf ("%d %d\n", x, y);   ans[cca (x, y)] ++;  }  for(i = 1; i <= n; i ++)  {   if(ans[i])    printf ("%d:%d\n", i, ans[i]);  } } return 0;}

评论