一个是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;
}

评论