这道题就是传说中的LCA了,从网上找了一个模板,用数组模拟的树
大概的原理, 大概就是:首先,把每个节点的祖先标记为自己,如果在一个子树内没有解决查询的LCA问题,那么该子树的所有节点的都将直接或间接的指向该子树的直接父亲,也就是子树内的所有节点的祖先都是该子树的父亲,然后就可以在该父亲的其他儿子中寻找。
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1000000000
using namespace std;
const int MAXN = 10005;
struct Tree
{
int head[MAXN];
int next[MAXN];
int node[MAXN];
int pos;
Tree()
{
clear();
}
void clear()
{
memset(head, -1, sizeof(head));
pos = 0;
}
void add(int s, int e)
{
node[pos] = e;
next[pos] = head[s];
head[s] = pos++;
}
}tree;
bool v[MAXN];
int in[MAXN];
int father[MAXN];
int x, y;
int find(int x)
{
if(father[x] == x) return x;
int t = find(father[x]);
father[x] = t;
return t;
}
void LCA(int u)
{
father[u] = u;//当访问到一个点的时候,先将其自己形成一个集合
for(int i = tree.head[u]; i != -1; i = tree.next[i])
{
LCA(tree.node[i]); //依次对子节点进行访问并处理
father[tree.node[i]] = u; //在处理完后,将子节点的集合链接到父节点
}
v[u] = 1; //标记访问过该点
if(u == x && v[y]) //如果当前点是查询中两点中的一点并且另外一点已经访问过,那么另一点的祖先即为公共祖先
{
printf("%d\n", find(y));
return;
}
else if(u == y && v[x])
{
printf("%d\n", find(x));
return;
}
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
memset(v, 0, sizeof(v));
memset(in, 0, sizeof(in));
tree.clear();
int n, s, e;
scanf("%d", &n);
for(int i = 1; i < n; i++)
{
scanf("%d%d", &s, &e);
tree.add(s, e);
in[e]++;
}
scanf("%d%d", &x, &y);
for(int i = 1; i <= n; i++)
{
if(in[i] == 0)
{
LCA(i);
break;
}
}
}
return 0;
}
分享到:
相关推荐
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ2942-Knights of the ...【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:http://blog.csdn.net/lyy289065406/article/details/6642573
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
动态规划 poj Common Subsequence c++ cpp文件
NULL 博文链接:https://128kj.iteye.com/blog/1754756
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2763 程序 线段树 LCA 2000MS AC
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)