POJ 1330 Nearst Common Ancestors(LCA)
テーマの種類 簡単なLCA
タイトルの意味
一本の木を与えて、ペアの点のLCAはどれですか?
問題の解き方
タルジャンアルゴリズムが使用できます.
参照コード - 疑問点がありますが、下のメッセージを見たらすぐに返事します.
タイトルの意味
一本の木を与えて、ペアの点のLCAはどれですか?
問題の解き方
タルジャンアルゴリズムが使用できます.
参照コード - 疑問点がありますが、下のメッセージを見たらすぐに返事します.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 10000 + 10;
vector<int>E[maxn];
int qu, qv, ans, fa[maxn], N[maxn];
bool vis[maxn];
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
void dfs(int u) {
if(ans != -1) return ;
fa[u] = u;
for( int i=0; i<E[u].size(); i++ ) {
int v = E[u][i];
dfs(v);
fa[v] = u;
}
vis[u] = true;
if(u == qu && vis[qv]) ans = find(qv);
if(u == qv && vis[qu]) ans = find(qu);
}
int main() {
freopen("in", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
for( int i=0; i<n; i++ ) E[i].clear(), N[i] = 0;
for( int i=0; i<n-1; i++ ) {
int u, v;
scanf("%d%d", &u, &v);
u--, v--;
N[v]++;
E[u].push_back(v);
}
scanf("%d%d", &qu, &qv);
qu--, qv--;
int rt;
for( int i=0; i<n; i++ ) if(N[i] == 0) rt = i;
ans = -1;
memset(vis, 0, sizeof(vis));
dfs(rt);
printf("%d
", ans+1);
}
return 0;
}