盒子

[poj1330]Nearest Common Ancestors_LCA_tarjan离线算法

hihocoder成功又在第八周上卡一天了( ̄ε(# ̄)☆╰╮( ̄▽ ̄///)…
于是滚来继续学基础…
题目:Nearest Common Ancestors
LCA问题,不过由于只查询一次,看不出来离线算法的优势呢
给一个离线算法的GOTO
一句话总结:如果我们在访问完节点u及其后代后,将u的祖先指向为x,那么在访问x的其它后代节点v时,LCA(u,v)就为u的(当前的)祖先点x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
const int mx = 10005;
vector<int> son[mx];
int fa[mx],query[mx];
bool vis[mx],hasroot[mx],ok;
int f(int x){
if(x==fa[x])return x;
return fa[x]=f(fa[x]);
}
//another more beautiful writing[orzing...
//int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void tarjan(int u){
int v;
if(ok)return;
vis[u]=true;
v=query[u];
if(v && vis[v]){
ok=true;
printf("%d\n",f(v));
return;
}
for(int i=1;i<=son[u][0];i++){
if(ok)return;
v=son[u][i];
tarjan(v),fa[v]=u;
}
}
int main(){
int t,a,b,n;
scanf("%d",&t);
while(t--){
ok=false;
memset(vis,0,sizeof(vis));
memset(hasroot,0,sizeof(hasroot));
memset(query,0,sizeof(query));
scanf("%d",&n);
for(int i=1;i<=n;i++){
fa[i]=i;
son[i].clear();
son[i].push_back(0);//remember it is not pushback but push_back [jiong face]
}
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
son[a][0]++;
son[a].push_back(b);
hasroot[b]=true;
}
scanf("%d%d",&a,&b);
query[b]=a,query[a]=b;
for(int i=1;i<=n;i++)if(!hasroot[i]){tarjan(i);break;}
}
return 0;
}