最近公共祖先-------4.28(没整理完)

最近公共祖先:在一个有根树中,结点u、v的最近公共祖先是满足是u,v的公共祖先并且深度尽可能大的结点。

1、倍增法

首先如果两个点的深度如果不同,将深度较大的点跳到与深度较小的点一样的深度,再同时向上跳,首次相遇时即为最近公共祖先。

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+15;
vector<int>vec[maxn];//记录树的边
int n,m,x,y,p,q,t;
int dad[maxn][maxn],deep[maxn];//dad i j 为结点i的第2^j个祖先;
int lca(int x,int y)
{
    if(deep[x]>deep[y])swap(x,y);//将深度小的结点前置
    for(int i=20;i>=0;i--){if(deep[dad[y][i]]>=deep[x])y=dad[y][i];}//滚动到相同的深度
    if(x==y)return x;
    for(int i=20;i>=0;i--){if(deep[dad[x][i]]!=deep[dad[y][i]]){x=dad[x][i],y=dad[y][i];}}//一起倍增找祖先
    return dad[x][0];
}
void dfs(int x)
{
    deep[x]=deep[dad[x][0]]+1;//深度为其爸爸的深度+1
    for(int i=0;dad[x][i];i++)
    dad[x][i+1]=dad[dad[x][i]][i];//滚动赋值,如果结点x的第2^i个祖先存在,那么x的第2^(i+1)个祖先=结点x的第2^i个祖先再往前面2^i个祖先。
    for(int i=0;i<vec[x].size();i++)
        if(!deep[vec[x][i]]){dad[vec[x][i]][0]=x;dfs(vec[x][i]);}//记录爸爸 深搜
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs(1);
    while(t--)
    {
        scanf("%d%d",&p,&q);
        printf("%d\n",lca(p,q));
    }
    return 0;
}

2、树剖法
size x为以x为结点的子树的结点的个数 每个结点和它的儿子之间只有一条重边,这个重边连向它的儿子中size最大的那个儿子。

如果结点u和它的儿子v之间是一条轻边,那么sizev*2<size u,因为这个儿子一定分不到它爸爸size的一半嘛。

top i 记录i结点所在链的链头,如果top u !=top v 说明u v不在一条链上 将 u=dad[u],重复上述操作;当它们在一条链上时,深度较小的那个点为他们的lca;

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+15;
vector<int>vec[maxn];
int m,n,x,y,p,q,t;
int deep[maxn],size[maxn],dad[maxn],top[maxn];
void dfs(int x)
{
    size[x]=1;deep[x]=deep[dad[x]]+1;
    for(int i=0;i<vec[x].size();i++)
    {
        if(dad[x]!=vec[x][i])
        {
            dad[vec[x][i]]=x;
            dfs(vec[x][i]);
            size[x]+=size[vec[x][i]];//加上它儿子的size
        }
    }
}
void dfs1(int x)
{
    int s=0;
    if(!top[x])top[x]=x;//先让每个链头赋值它本身
    for(int i=0;i<vec[x].size();i++)
    {
        if(dad[x]!=vec[x][i]&&size[vec[x][i]]>size[s])s=vec[x][i];//寻找size最大的儿子
    }
    if(s)//能找到size最大的儿子
    {
     top[s]=top[x];//他的儿子结点的链头赋值上它爹
     dfs1(s);//继续找重边
    }
    for(int i=0;i<vec[x].size();i++)
    {
        if(dad[x]!=vec[x][i]&&vec[x][i]!=s)dfs1(vec[x][i]);//深搜它的轻边的结点里的重边
    }
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];)//不在一个链上
    {
    if(deep[top[x]]<deep[top[y]])swap(x,y);
    x=dad[top[x]];//将较深点赋值为他链头的爸爸;
    }
    if(deep[x]>deep[y])swap(x,y);//深度小的结点为lca
    return x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs(1);//赋值size deep dad
    dfs1(1);//找重链 轻链
    while(t--)
    {
        scanf("%d%d",&p,&q);
        printf("%d\n",lca(p,q));
    }
    return 0;
}

3、tarjian法

时间: 04-30

最近公共祖先-------4.28(没整理完)的相关文章

简单的数据结构5.1--------(没整理完)

1.栈 (1)栈的模拟 特点:先进后出 eg1:火车进站 实际就是模拟一个栈 #include<bits/stdc++.h> using namespace std; const int maxn=1000; int Stack[maxn],a[maxn],stack[maxn],n,l=1; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",a+i); for(int

Java 动态代理是基于什么原理(还没整理完)

1> Java的反射机制在平时的业务开发过程中很少用到,但是在一些基础框架的搭建上应用非常广泛 2>什么是Java反射机制 Java反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法:对于任意一个对象,都能够调用它的任意方法和属性:这种动态获取信息以及动态调用对象方法的功能称为java语言的反射机制. 3>反射机制提供了哪些功能 ----在运行时判定任意一个对象所属的类 ----在运行时构造任意一个类的对象 ----在运行时判定任意一个类所具有的成员变量和方法 --

最近公共祖先(LCA)问题

描述 对于有根树T的两个节点u和v,最近公共祖先LCA(T,u,v)表示一个节点x满足x是u,v的公共祖先且x的深度尽可能大. 算法 求解LCA问题主要有三种解法,分别是暴力搜索,Tanjar算法,最后一种是转化为RMQ问题,用DFS+ST算法来求解 暴力搜索 如果数据量不大的时候可以采用暴力搜索法.先将节点u的祖先节点全部标记出来,然后顺着节点v沿着父亲节点的方向向上遍历,直到遍历到一个被标记的节点,这个节点即为所求节点.或者分别获取u,v到根节点的路径P1,P2,可以将这两条路径看做两个两个

[leetcode]236. Lowest Common Ancestor of a Binary Tree二叉树最近公共祖先

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q

笔记:LCA最近公共祖先 Tarjan(离线)算法

LCA最近公共祖先 Tarjan他贱(离线)算法的基本思路及其算法实现 本文是网络资料整理或部分转载或部分原创,参考文章如下: https://www.cnblogs.com/JVxie/p/4854719.html http://blog.csdn.net/ywcpig/article/details/52336496 https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin 最近公共祖先简称LCA(Lowest Common Ancesto

LCA(最近公共祖先)--tarjan离线算法 hdu 2586

HDU 2586 How far away ? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11320    Accepted Submission(s): 4119 Problem Description There are n houses in the village and some bidirectional roads c

Solution: 最近公共祖先&#183;一 [hiho一下 第十三周]

题目1 : 最近公共祖先·一 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho最近发现了一个神奇的网站!虽然还不够像58同城那样神奇,但这个网站仍然让小Ho乐在其中,但这是为什么呢? “为什么呢?”小Hi如是问道,在他的观察中小Ho已经沉迷这个网站一周之久了,甚至连他心爱的树玩具都弃置一边. “嘿嘿,小Hi,你快过来看!”小Ho招呼道. “你看,在这个对话框里输入我的名字,在另一个对话框里,输入你的名字,再点这个查询按钮,就可以查出来……什么!我们居然有同一个

数据结构问题集锦 - 最小公共祖先问题

作为一个工程党,在各路竞赛大神的面前总会感到自己实力的捉急.大神总是能够根据问题的不同,轻而易举地给出问题的解法,然而我这种渣渣只能用所谓的”直观方法“聊以自慰,说多了都是泪啊.However,正视自己理论方面的不足,迎头赶上还是必要的,毕竟要真正踏入业界,理论知识是不能少的啊.(比如各种语言的Hash Map,它们的核心可都是红黑树啊) 既然助教要求博文要直观,通俗易懂,那就让我们递归这种方法开始.方法一:递归法 按照题目的要求,如果某两个节点具有同一个公共祖先的话,那么会存在两种情况:要么其

[转]LCA 最近公共祖先

原文传送门orzJVxie Tarjan(离线)算法的基本思路及其算法实现 首先是最近公共祖先的概念(什么是最近公共祖先?): 在一棵没有环的树上,每个节点肯定有其父亲节点和祖先节点,而最近公共祖先,就是两个节点在这棵树上深度最大的公共的祖先节点. 换句话说,就是两个点在这棵树上距离最近的公共祖先节点. 所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径. 有人可能会问:那他本身或者其父亲节点是否可以作为祖先节点呢? 答案是肯定的,很简单,按照人的亲戚观念来说,你的父亲也是你的祖