POJ.1330 Nearest Common Ancestors

1.Problem
http://poj.org/problem?id=1330

2.Idea
while(x!=y) {
     if(depth x < depth y) y = parent of y;
     else  x = parent of x;
}

3.Source

 const int N = 10000;  
 vector<int> a[N]; // multiple linked list, the list of children for node i is a vector  
 int f[N], r[N]; // representations of parents and hierarchy, the parent and hierarchy for node i is f[i] and r[i]  
 void DFS(int u, int dep) // Pre-order Traversal from node u  
 {  
      r[u] = dep; // node u is at hierarchy dep  
      for (vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it)  
           DFS(*it, dep + 1);// Recursion for every child of u  
 }  
 int main()  
 {  
      int casenum, num, n, i, x, y;  
      scanf("%d", &casenum); // number of test cases  
      for (num = 0; num < casenum; num++)  
      {  
           scanf("%d", &n); // number of nodes  
           for (i = 0; i < n; i++) a[i].clear(); //initialization  
           memset(f, 255, sizeof(f));  
           for (i = 0; i < n - 1; i++)  
           {  
                scanf("%d %d", &x, &y); // edge (x, y)  
                a[x - 1].push_back(y - 1); // push node (y-1) into the list of (x - 1)’s children  
                f[y - 1] = x - 1; //node(y-1)’s parent is (x-1)  
           }  
           for (i = 0; f[i] >= 0; i++); // search the root i  
           DFS(i, 0); // calculate every nodes’ hierarchy from the root  
           scanf("%d %d", &x, &y); // a pair of nodes  
           x--; y--;  
           while (x != y) // to find the Nearest Common Ancestors  
           {  
                if (r[x]>r[y]) x = f[x];  
                else y = f[y];  
           }  
           printf("%d\n", x + 1);// Output  
      }  
      return 0;  
 }