LCA 学习小记 Poj 1330 Nearest Common Ancestors

心已赠人 2022-09-19 15:26 139阅读 0赞

LCA：最近公共祖先(Least Common Ancestors)

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。

解决LCA问题主要有两种方法：基于RMQ的在线算法，基于并查集的tarjan离线算法。

在线算法：用比较长的时间做预处理，但是等信息充足以后每次回答询问只需要用比较少的时间。

离线算法：先把所有的询问读入，然后一起把所有询问回答完成。

目前对离线算法掌握的还不好，这几天再练练吧。

**在线算法**

在线算法DFS+ST描述(思想是：将树看成一个无向图，u和v的公共祖先一定在u与v之间的最短路径上)：

（1）从树根开始DFS，按照DFS的顺序，记录DFS的每一步遍历到的节点和该节点的深度（分别是F数组和B数组）

（2）记录每个节点第一次被遍历到时的序号和在搜索树中的深度（id和dep数组）；

（3）建立RMQ数组：设t=RMQ\[i\]\[j\]，表示遍历序号在\[i,i+2^j-1\]区间内最小的深度为B\[t\](B数组如（1）中所指)；

（4）查询节点a和节点b的最近公共祖先：用（2）中的id数组可以得到节点在搜索树中的序号，设a=id\[a\],b=id\[b\],接着使用（3）中的RMQ数组可以得到区间\[a,b\]内深度最小的遍历序号，进而使用该序号和F数组可以得到深度最小的节点， 即a和b的最近公共祖先。

【举例说明】

T=<V,E>，其中V=\{A,B,C,D,E,F,G\},E=\{AB,AC,BD,BE,EF,EG\},且A为树根。则图T的DFS结果为：A->B->D->B->E->F->E->G->E->B->A->C->A，要求D和G的最近公共祖先, 则LCA\[T, D, G\] = RMQ(L, R\[D\], R\[G\])= RMQ(L, 3, 8)，L中第4到7个元素的深度分别为：1,2,3,3，则深度最小的是B。

#include <cstdio>
    #include <cmath>
    #include <cstring>
    
    const int N=10005;  //节点数量
    struct node
    {
    	int v,next;
    }edges[N<<1];
    
    int head[N],e;
    int pre[N],dep[N];
    int id[N]; //节点第一次被遍历的顺序
    int RMQ[N*3][20];
    int curID;
    //F[i]表示第i个遍历的节点
    //B[i]表示F[i]在树中的深度
    int F[N*3],B[N*3];
    
    
    int n,Q,root;
    bool in[N]; //用入度判断那个点是树根
    
    void Add (int u,int v)
    {
    	edges[e].v=v;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    void DFS (int u,int p,int Dep)
    {
    	int i,v;
    	curID++;
    	F[curID]=u;
    	B[curID]=Dep;
    	id[u]=curID;
    	pre[u]=p;
    	dep[u]=Dep;
    	for (i=head[u];i!=-1;i=edges[i].next)
    	{
    		v=edges[i].v;
    		if (v==p) continue;
    		DFS(v,u,Dep+1);
    		curID++;
    		F[curID]=u;
    		B[curID]=Dep;
    	}
    }
    
    void initRMQ ()
    {
    	int i,j,x,y;
    	for (i=1;i<=curID;i++)
    		RMQ[i][0]=i;
    	for (j=1;(1<<j)<=curID;j++)
    		for (i=1;i+(1<<j)-1<=curID;i++)
    		{
    			x=RMQ[i][j-1];
    			y=RMQ[i+(1<<(j-1))][j-1];
    			RMQ[i][j]=B[x]<B[y]?x:y;
    		}
    }
    
    int getLCA (int a,int b)
    {
    	int k,x,y;
    	a=id[a];b=id[b];
    	if (a>b)
    		k=a,a=b,b=k;
    	k=log(1.0+b-a)/log(2.0);
    	x=RMQ[a][k];
    	y=RMQ[b-(1<<k)+1][k];
    	return B[x]<B[y]?F[x]:F[y];
    }
    
    void Build ()
    {
    	curID=0;
    	memset(head,-1,sizeof(head));
    	e=0;
    	int u,v;
    	memset (in,false,sizeof(in));
    	for (int i=1;i<n;i++)
    	{
    		scanf("%d%d",&u,&v);
    		Add(u,v);
    		in[v]=true;
    	}
    	for (root=1;in[root];root++);
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		Build();
    		DFS(root,0,0);
    		initRMQ();
    		int u,v;
    		scanf("%d%d",&u,&v);
    		printf("%d\n",getLCA(u,v));
    	}
    	return 0;
    }

**离线算法**

离线算法是将所有的树中的边和询问全部读入，每次在遍历完一个节点v后，将v和父节点u合并，这中间要用到并查集。  
每次遍历完u的全部子节点后，若有询问(u,v)，则判断v是否已经被访问过，若被访问过，则v的根节点就是u和v的LCA。

以下参考自：http://blog.csdn.net/miaolinjie/article/details/8348664

算法大体流程如下：对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v所在集合的祖先。

也就是说：每次遍历完u的全部子节点后，若有询问(u,v)，则判断v是否已经被访问过，若被访问过，则v的根节点就是u和v的LCA。

【举例说明】

根据实现算法可以看出，只有当某一棵子树全部遍历处理完成后，
    才将该子树的根节点标记为黑色（初始化是白色），假设程序按上面的树形结构进行遍历，首先从节点1开始
    ，然后递归处理根为2的子树，当子树2处理完毕后，节点2， 5， 6均为黑色；接着要回溯处理3子树，首先被染黑的是节点7
    （因为节点7作为叶子不用深搜，直接处理），接着节点7就会查看所有询问(7, x)的节点对，假如存在(7, 5)，因为节点5已经被染黑，
    所以就可以断定(7, 5)的最近公共祖先就是find(5).ancestor，即节点1（因为2子树处理完毕后，子树2和节点1进行了union，find(5)返回了合并后的树的根1，
    此时树根的ancestor的值就是1）。有人会问如果没有(7, 5)，
    而是有(5, 7)询问对怎么处理呢? 我们可以在程序初始化的时候做个技巧，将询问对(a, b)和(b, a)全部存储，这样就能保证完整性。

#include <cstdio>
    #include <cmath>
    #include <cstring>
    
    const int N=10005;  //节点数量
    struct node
    {
    	int v,next;
    }edges[N<<1];
    
    int head[N],e;
    int set[N];
    bool visit[N],in[N];
    int n,Q,root,ans,U,V;
    
    void Add (int u,int v)
    {
    	edges[e].v=v;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    int Find (int x)
    {
    	if (set[x]!=x)
    		set[x]=Find(set[x]);
    	return set[x];
    }
    
    void Union (int x,int y)
    {
    	x=Find(x);
    	y=Find(y);
    	if (x==y)
    		return;
    	set[y]=x;
    }
    
    void DFS (int u,int p)
    {
    	int i,v;
    	for (i=head[u];i!=-1;i=edges[i].next)
    	{
    		v=edges[i].v;
    		if (v==p)
    			continue;
    		DFS(v,u);
    		Union(u,v);
    	}
    	if (ans!=-1)
    		return;
    	visit[u]=true;
    	if (U==u)
    	{
    		if (visit[V])
    			ans=Find(V);
    	}
    	else if (V==u)
    	{
    		if (visit[U]) ans=Find(U);
    	}
    }
    
    void Build ()
    {
    	int i,u,v;
    	memset(in,false,sizeof(in));
    	memset(head,-1,sizeof(head));
    	e=0;
    	for(i=1;i<n;i++)
    	{
    		scanf("%d%d",&u,&v);
    		Add(u,v);
    		in[v]=true;
    	}
    	for (root=1;in[root];root++);
    	for (i=1;i<=n;i++)
    		set[i]=i;
    	memset(visit,0,sizeof(visit));
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		Build();
    		scanf("%d%d",&U,&V);
    		ans=-1;
    		DFS(root,-1);
    		printf("%d\n",ans);
    	}
    	return 0;
    }