任意门：http://poj.org/problem?id=1330
Nearest Common Ancestors
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 34942 | Accepted: 17695 |
Description
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
Output
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
题意概括：
给一棵有N个节点，N-1条边的树 和 一对结点，求这对结点的最近公共祖先。
解题思路：
找根结点用一个标记数组
找公共祖先用简单粗暴的 Tarjan。
AC code：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = 1e4+;
struct Edge{int v, next;}edge[MAXN<<];
int head[MAXN], cnt;
int fa[MAXN];
bool in[MAXN];
bool vis[MAXN];
int N, M, S, ans, a, b; inline void init()
{
memset(head, -, sizeof(head));
memset(vis, false, sizeof(vis));
memset(in, false, sizeof(in));
cnt = ;
} inline void AddEdge(int from, int to)
{
edge[cnt].v = to;
edge[cnt].next = head[from];
head[from] = cnt++;
} int findset(int x)
{
int root = x;
while(fa[root] != root) root = fa[root]; int tmp;
while(fa[x] != root){
tmp = fa[x];
fa[x] = root;
x = tmp;
}
return root;
} void Tarjan(int s)
{
fa[s] = s;
for(int i = head[s]; i != -; i = edge[i].next){
int Eiv = edge[i].v;
Tarjan(Eiv);
fa[findset(Eiv)] = s;
}
vis[s] = true;
if(s == a){
if(vis[a] && vis[b]) ans = findset(b);
}
else if(s == b){
if(vis[a] && vis[b]) ans = findset(a);
}
} int main()
{
int T_case, u, v;
scanf("%d", &T_case);
while(T_case--)
{
init();
scanf("%d", &N);
M = N-;
for(int i = ; i <= M; i++){
scanf("%d %d", &u, &v);
AddEdge(u, v);
in[v] = true;
//AddEdge(v, u);
}
scanf("%d %d", &a, &b);
int root = ;
for(int i = ; i <= N; i++){
if(!in[i]){root = i;break;}
}
Tarjan(root);
printf("%d\n", ans);
}
return ;
}