POJ 1330 - Nearest Common Ancestors

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

概要

N 個のノードからなる根付き木が与えられる． その木のあるノードと別のあるノードのいわゆる LCA を答える．

制約

• 2 <= N <= 10000

解法

Spaghetti Source のアルゴリズムをそのまま使った．

  1 #include <cstdio>
  2 #include <vector>
  3 using namespace std;
  4 
  5 class DisjointSet { // {{{
  6   private:
  7     vector<int> parent;
  8 
  9   public:
 10     DisjointSet(int s) : parent(s, -1) {}
 11 
 12     int root(int x)
 13     {
 14       if (parent[x] < 0) {
 15         return x;
 16       } else {
 17         parent[x] = root(parent[x]);
 18         return parent[x];
 19       }
 20     }
 21 
 22 
 23     bool unite(int x, int y)
 24     {
 25       const int a = root(x);
 26       const int b = root(y);
 27       if (a != b) {
 28         if (parent[a] < parent[b]) {
 29           parent[a] += parent[b];
 30           parent[b] = a;
 31         } else {
 32           parent[b] += parent[a];
 33           parent[a] = b;
 34         }
 35         return true;
 36       } else {
 37         return false;
 38       }
 39     }
 40 
 41     bool find(int x, int y)
 42     {
 43       return root(x) == root(y);
 44     }
 45 
 46     int size(int x)
 47     {
 48       return -parent[root(x)];
 49     }
 50 };  // }}}
 51 
 52 void tarjan_visit(const vector<vector<int> >& g, int u, int x, int y, vector<bool>& color, vector<int>& ancestor, DisjointSet& s, int& ans)
 53 {
 54   ancestor[s.root(u)] = u;
 55   for (vector<int>::const_iterator it(g[u].begin()); it != g[u].end(); ++it) {
 56     tarjan_visit(g, *it, x, y, color, ancestor, s, ans);
 57     s.unite(u, *it);
 58     ancestor[s.root(u)] = u;
 59   }
 60   color[u] = true;
 61   int w = -1;
 62   if (u == x) {
 63     w = y;
 64   } else if (u == y) {
 65     w = x;
 66   }
 67   if (w != -1 && color[w]) {
 68     ans = ancestor[s.root(w)];
 69   }
 70 }
 71 
 72 int tarjan(const vector<vector<int> >& g, int root, int x, int y)
 73 {
 74   DisjointSet s(g.size());
 75   vector<bool> color(g.size());
 76   vector<int> ancestor(g.size());
 77   int ans;
 78   tarjan_visit(g, root, x, y, color, ancestor, s, ans);
 79   return ans;
 80 }
 81 
 82 int main()
 83 {
 84   int T;
 85   scanf("%d", &T);
 86   while (T-- > 0) {
 87     int N;
 88     scanf("%d", &N);
 89     vector<vector<int> > g(N);
 90     vector<int> deg(N, 0);
 91     for (int i = 0; i < N-1; i++) {
 92       int u, v;
 93       scanf("%d %d", &u, &v);
 94       --u;  --v;
 95       g[u].push_back(v);
 96       ++deg[v];
 97     }
 98     int root = -1;
 99     for (int i = 0; i < N; i++) {
100       if (deg[i] == 0) {
101         root = i;
102       }
103     }
104 
105     int x, y;
106     scanf("%d %d", &x, &y);
107     --x;  --y;
108     printf("%d\n", tarjan(g, root, x, y)+1);
109   }
110   return 0;
111 }