关于离线算法（tarjan）的lca

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n;
int father[105];                            //每个节点的父节点  
int rnk[105];                               //树中节点的个数  
int ancestor[105];                          //已访问节点集合的祖先  

void initSet() {
	for (int i = 0; i<n; i++) {
		father[i] = i;                      //初始化时，所在子树的祖先就是自己  
		rnk[i] = 1;                         //所在树的深度为0  
	}
}

int findSet(int x) {
	if (x != father[x])
		father[x] = findSet(father[x]);     //压缩式的查找，在查找过程中更新每个节点的祖先  
	return father[x];
}

void unionSet(int x, int y) {               //合并子树,把节点数小的树合并到节点数大的树  
	x = findSet(x);
	y = findSet(y);

	if (x == y)
		return;

	if (rnk[x] >= rnk[y]) {
		father[y] = x;
		rnk[x] += rnk[y];
	}
	else {
		father[x] = y;
		rnk[y] += rnk[x];
	}
}

int flag[105];                             //记录点是否为访问过  
vector<int> tree[105];                     //树的表示  
vector<int> query[105];                    //查询的表示  
void tarjan(int u)
{                        //访问到集合u时  
	for (int i = 0; i<tree[u].size(); i++) {
		int v = tree[u][i]; 
	//	cout << v << endl;//假设这个节点是v  
		tarjan(v);
		unionSet(u, v);                     //将子节点和根节点合并,并查集的作用只是代表一个集合，仅仅当做一个集合使用  
		ancestor[findSet(u)] = u;            //合并后的集合的祖先为u,只要标记这个集合的代表元素的祖先为x就行，这个集合  
											 //内的其他元素能够通过findSet来找到代表，再利用代表找到祖先  
	}
	flag[u] = 1;

	for (int i = 0; i<query[u].size(); i++)
	{
		if (flag[query[u][i]])               //如果另外一个节点已经被访问过，则输出另外一个节点所在集合的祖先  
			cout << u << "和" << query[u][i] << "的最近公共祖先为:" << ancestor[findSet(query[u][i])] << endl;  //找到节点query[u][i]所在集合的代表的祖先，
																									   //也就是这个集合的祖先，只是用代表的ancestor值标记一下而已   
	}
}
int main()
{
	initSet();
	tree[1].push_back(2);
	tree[1].push_back(3);
	tree[2].push_back(4);
	tree[3].push_back(5);
	query[4].push_back(5);
	query[5].push_back(4);
	tarjan(1);
	return 0;
}