近期公共祖先(LCA)——离线Tarjan算法+并查集优化

2022-07-21 13:57:36

一. 离线Tarjan算法

LCA问题(lowest common ancestors)：在一个有根树T中。两个节点和

e&sig=3136f1d5fcf75709d9ac882bd8cfe0cd" alt="">的近期公共祖先。指的是二者的公共祖先中深度最高的节点。

给定随意两个树中的节点，求它们的近期公共祖先。

对于二分查找树、二叉树，能够用普通的dfs实现。但对于多叉树、查询次数频繁的情况下。离线Tarjan算法的长处就显现出来了。因为对树上全部节点仅仅进行一次遍历，因此须要提前指定全部查询，所以才称为offline。

算法思路是：每次处理一个节点时。先递归处理其儿子节点，保证：若查询的节点pair均在该子树中，则处理完这个节点后，这些查询也已经处理完成，否则当中一个节点在还有一个子树中，这对节点的公共祖先至少应该是的父节点。详细是对每一个节点，都维护一个集合。每当一个节点处理完成，就与其父节点所在集合进行合并。处理完成指的是：以该节点为根节点的子树中的全部节点都被訪问过而且返回了。

因此以某个元素为代表元的集合内，保存的都是当前已经处理完成的子孙节点。

算法的伪代码例如以下：初始时每一个节点颜色均为white

LCA(u)

1	MakeSet(u)

2	u.ancestor := u

3	for each v in u.children do

4		LCA(v)

5		Union(u, v)

6		Find(u).ancestor := u

7	u.color := black;

8	for each v such that {u, v} in P do

9		if v.color == black

10			print "Tarjan's lowest common Ancestor of " + u +

				  " and " + v + " is " + Find(v).ancestor + "."</span>

以下首先对算法导论中的习题进行证明:

(1)证明：对每一对

%5C%5B%5Cleft%5C%7B%20%7Bu%2Cv%7D%20%5Cright%5C%7D%20%5Cin%20P%5C%5D&sig=99c9bd96a9879f7863bbb29a0a48cef6" alt="">，第10行恰运行一次

证明：由于每一个节点仅仅调用一次LCA，对随意节点对，不失一般性。如果先被处理完，则当的全部儿子都处理完。被置为Black，此时v仍为White。仅仅有当v处理完其子树，被置为Black。才干进入第10行的代码。因此对每一对查询。第10行仅仅运行一次。

(2)证明：在调用LCA(

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">)时，不相交集合数据结构中的集合数等于

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">在树T中的深度

证明:调用LCA(

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">)时。以为根的子树均没有被訪问。

如果是其父节点的第个儿子节点，则对全部儿子节点

%5C%5B%7Bc_j%7D%2Cj%20%3C%20i%5C%5D&sig=5cbbb471f265b890cb96928b74ec66d8" alt="">，因为这些节点已经处理完成并返回。都进行了的操作，因此这些子树中的节点与在同一个集合中。

而对节点来说，其子树并未处理完成。所以对于

p&sig=5e55d6bf1a1217b54bed34d5562fa2f6" alt="" style="font-size:18px; text-align:justify; text-indent:24px">的调用LCA()并没有返回。因此

p&sig=5e55d6bf1a1217b54bed34d5562fa2f6" alt="" style="font-size:18px; text-align:justify; text-indent:24px">和其父节点在不同的集合中，同理能够一直推到根节点。

因此当前的集合数等于在树T中的深度。

(3)证明：对每一对

%5C%5B%5Cleft%5C%7B%20%7Bu%2Cv%7D%20%5Cright%5C%7D%20%5Cin%20P%5C%5D&sig=99c9bd96a9879f7863bbb29a0a48cef6" alt="" style="font-size:18px; text-align:justify; text-indent:36px">。LCA能正确的输出和的最小公共祖先

证明：

①若

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">和在同一条路径中，不失一般性。如果为的祖先节点。则节点返回后两个节点均为BLACK，输出

%5C%5Bu.ancestor%20%3D%20u%5C%5D&sig=dfbe3eefa77af29d346fc066dbade8c6" alt="">。正确

②否则，如果二者的近期公共祖先为

r&sig=2843a46acedae61753b8f0e390549a9b" alt="">，设

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">在第

i&sig=e85d4cccfe4d36369f658677663a0804" alt="">个分支上。在第

j&sig=c652b11939bb8d14cfcf73c2f685080c" alt="">个分支上()，那么先被訪问到，在第9行代码处，因为尚未处理仍为White，所以返回，所在集合与其父节点所在集合Union，回到时集合代表元的ancestor被置为，然后才干继续处理。处理完

v&sig=8bd98ac88d83cc372cec42fde5c932eb" alt="" style="font-size:18px; text-align:justify; text-indent:24px">时，进入第9行代码，此时的

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">颜色已经为BLACK，输出。得到正确答案。

综上，LCA能正确输出

u&sig=57f503cbf2e8bee62f4b7018d46a58b8" alt="" style="font-size:18px; text-align:justify; text-indent:24px">和的最小公共祖先。

二. 并查集优化——不相交集合森林

由于当中涉及到集合操作，因此使用了并查集来优化。并查集能够使用更快的实现。用有根树表示集合，每一个成员仅指向其父节点，每棵树的根包括集合的代表元素，代表元的父节点是其本身。

通过引入两种启示式策略（Union的时候按秩合并，Find的时候进行路径压缩）。能得到渐进最优的不相交集合数据结构。

按秩合并：在Union的时候，经常会碰到两个集合元素个数不一样，显然将小的集合纳入大的集合，操作成本更低。

由于使用的是有根树来表示集合，所以自然地能够用根节点（代表元）的高度来表示，这个就称为秩(rank)。在Union的过程中，让具有较小秩的根指向具有较大秩的根。若二者具有同样的秩，则任取当中一个作为父节点，并对它的秩加1。

（由于此时树的高度添加了1）。

路径压缩：普通的Find算法直接沿着节点路径向上查找到根。对一个具有n个节点的路径来说，对这n个节点都进行Find操作，每一个节点都须要沿着父节点搜到根。须要的操作。而优化的方法是：找到根之后。对这条查找路径上的节点，都将其父节点更新为根节点，即：一次Find操作将导致这条路径上的节点都直接指向根。

伪代码例如以下：

MakeSet(x)

	x.p = x

	x.rank = 0

Union(x, y)

	xRoot = Find(x)

	yRoot = Find(y)

	if xRoot.rank > yRoot.rank

		yRoot.p = xRoot

	else

		xRoot.p = yRoot

		if xRoot.rank == yRoot.rank

			yRoot.rank = yRoot.rank + 1

Find(x)

	if x.p != x

		x.p = return Find(x.p)

	return x.p;

实际中Find能够用迭代取代递归。实际coding时要注意，parent这一结构是在并查集中用到的。ancestor是LCA算法中的，二者不能等同，而且ancestor也不是代表元，ancestor指的是代表元所在集合中全部节点的公共祖先。

题目：http://poj.org/problem?

id=1330 ，AC代码例如以下：

#include <iostream>

#include <cstring>

using namespace std;

#define N 10005

struct Edge{

	int to, next;

};

Edge e[N];

struct Node{

	int pa, rank;

	Node() : pa(0), rank(0) {}

};

Node nodes[N];

int head[N], cnt, q1, q2, ancestor[N];

bool hasp[N], color[N];

void add(int from, int to){

	e[cnt].to = to, e[cnt].next = head[from], head[from] = cnt;

	++cnt;

}

void make_set(int u){

	nodes[u].pa = u;

	nodes[u].rank = 0;

}

int find_set(int u){

	int root = u;

	while(nodes[root].pa != root)

		root = nodes[root].pa;

	int cur;

	while(u != root){

		cur = nodes[u].pa;

		nodes[u].pa = root;

		u = cur;

	}

	return root;

}

void union_set(int x, int y){

	int xr = find_set(x), yr = find_set(y);

	if (nodes[xr].rank > nodes[yr].rank)

		nodes[yr].pa = xr;

	else{

		nodes[xr].pa = yr;

		if(nodes[xr].rank == nodes[yr].rank)

			++nodes[yr].rank;

	}

}

bool LCA(int u){

	make_set(u);

	ancestor[u] = u;

	for(int i = head[u]; i; i = e[i].next){

		int v = e[i].to;

		if(LCA(v))

			return true;

		union_set(u, v);

		ancestor[find_set(u)] = u;

	}

	color[u] = true;

	bool fin = false;

	if(u == q1 && color[q2])

		cout << ancestor[find_set(q2)] << endl, fin = true;

	else if(u == q2 && color[q1])

		cout << ancestor[find_set(q1)] << endl, fin = true;

	return fin;

}

int main(){

	int tc;

	cin >> tc;

	while(tc --){

		int n;

		cin >> n;

		memset(head, 0, sizeof(head));

		memset(ancestor, 0, sizeof(ancestor));

		memset(color, false, sizeof(color));

		memset(hasp, false, sizeof(hasp));

		cnt = 1;

		for(int i = 1; i < n; ++i){

			int p, c;

			cin >> p >> c;

			add(p, c);

			hasp[c] = true;

		}

		cin >> q1 >> q2;

		int root = 0;

		for(int i = 1; i <= n; ++i){

			if(!hasp[i]){

				root = i;

				break;

			}

		}

		LCA(root);

	}

	return 0;

}

码农公寓

一. 离线Tarjan算法

二. 并查集优化——不相交集合森林

相关文章