POJ 1330 Nearest Common Ancestors 【用Tarjan求LCA】

2019-11-06 07:02:52

字体：大中小

来源：转载

供稿：网友

题目链接：http://poj.org/PRoblem?id=1330

题意：有一棵树，n个结点n-1条边，给你这几条边的信息，再给你两个点，求这两个点的LCA（最近公共祖先）题解：一道小题，直接用Tarjan就水过去了，注意细节！

代码：

#include <cstdio>#include <vector>#include <cstring>using namespace std;const int size = 3e5+5;vector<int> tree[size];int n, qa, qb, deg[size], vis[size], root;int fath[size];int get(int x) { if(fath[x] == x) return fath[x]; return fath[x] = get(fath[x]);}void Unionset(int x, int y) { int fx = get(x), fy = get(y); if( fx == fy ) return ; fath[fy] = fx;}void init() { for ( int i = 0; i <= n; i ++ ) fath[i] = i;}int ans = 0;void Tarjan(int rt) { for ( int i = 0; i < tree[rt].size(); i ++ ) { Tarjan(tree[rt][i]); Unionset(rt, tree[rt][i]); } vis[rt] = 1; if(rt == qa) { if(vis[qb]) { ans = get(qb); return ; } } if(rt == qb) { if(vis[qa]) { ans = get(qa); return ; } }}int main() { // freopen("1330.in","r",stdin); int tst; scanf("%d", &tst); while(tst--){ memset(deg, 0, sizeof(deg)); memset(vis, 0, sizeof(vis)); scanf("%d",&n); init(); for ( int i = 0; i <= n; i ++ ) tree[i].clear(); for ( int i = 0; i < n-1; i ++ ) { int u, v; scanf("%d %d", &u, &v); tree[u].push_back(v); // 有向边 deg[v] ++; } // 找树根 for ( int i = 1; i <= n; i ++ ) { if(deg[i] == 0) { root = i; break; } } scanf("%d %d", &qa, &qb); Tarjan(root); printf("%d/n", ans); } return 0;}

上一篇：linux学习历程

下一篇：浅谈WeakHashMap