本文是对http://noalgo.info/476.html的一点理解,特别是对其中
int father[mx]; //节点的父亲
int ancestor[mx]; //已访问节点集合的祖先
这两个数组作用的解释;
首先必须明确,并查集重建的树跟原来的树并不一样;
还是借用该文章的例子:
Tarjan算法是基于DFS(深度优先搜索), 图中的树深度优先遍历的顺序应该是:
->->->->->->->
但作者却说,节点的处理顺序为:
->->->->->->->
其实, 这里第一种顺序是我们处理查询请求的顺序,例如我们遍历到5, 则我们可以获得 5与5之前的所有已经遍历过的节点即(5,4) (5,7)的查询结果;
第二种顺序则是我们建立并查集的顺序
关键代码如下:
void Tarjan(int x) //Tarjan算法求解LCA
{
for (int i = ; i < tree[x].size(); i++)
{
Tarjan(tree[x][i]); //访问子树
unionSet(x, tree[x][i]); //将子树节点与根节点x的集合合并,这里是并查集处理节点x
ancestor[findSet(x)] = x;//合并后的集合的祖先为x
}
vs[x] = ; //标记为已访问, 这里是DFS遍历节点x
for (int i = ; i < query[x].size(); i++) //与根节点x有关的查询
if (vs[query[x][i]]) //如果查询的另一个节点已访问,则输出结果
printf("%d和%d的最近公共祖先为:%d\n", x,
query[x][i], ancestor[findSet(query[x][i])]);
}
两者顺序不同的原因在于下面的第6行和第9行代码,我们在还未遍历父节点的时候,处理第一个子树后,父节点就已经在并查集内了;例如我们还没有遍历节点1,在遍历节点4后,就会处理节点4与其父节点1的合并;
下面,我们来慢慢建立并查集的树;
第一步:
遍历过的元素{4}, 集合[4]{4}->4
第二步:
集合{4}与父节点{1}按秩合并, 合并后的集合为{4,1},集合代表元素为4,即father[4] = 4, father[1] = 4; 集合{4,1}的公共祖先为1,ancestor[4] = 1; 即这个集合的代表元素并不是它的公共祖先
第三步:
遍历过的元素有{4,7}, 有两个集合[4]{4,1}和[7]{7}, ([]里面的元素为代表元素,{}的元素为集合内的所有元素), 此时, 若查询(7,4), 则4已经遍历过, 访问4所在集合的代表元素为 father[4], 集合4的公共祖先为ancestor[father[4]]
第四步:
遍历过的元素有{4,7,5}, 集合[7]{7}合并集合[5]{5}为[7]{7,5}, ancestor[7] = 5
.....
遍历完根节点的第一棵子树后, 集合[7]{4,1,5,7} 与根节点集合[0]{0}合并为[7]{0,1,4,5,7}, 即father[0]=7, 同时更新集合的公共祖先ancestor[7]=0;
最后遍历过的元素{4,7,5,1,2,6,3,0}, 集合为[7]{4,7,5,1,2,6,3,0}, ancestor[7] = 0
为方便理解,最后的图是没有经过路径压缩的, 实际上应该是所有元素的父节点皆为集合代表元素7