路径压缩的并查集：侦探PIPI

文章目录

路径压缩的并查集：侦探PIPI

路径压缩的并查集

并查集是一种用来管理元素分组情况的数据结构。它可以高效的完成:
（1）查询元素a和元素b是否属于同一分组
（2）合并元素a和元素b所在的组
可以把并查集看成一个树形结构，我们把树根作为这个分组的代表。使用数组fa来保存每个节点的父节点。查询两个元素属于同一组时，我们需要沿着树往上走找到树根，两个元素有同一个树根说明属于同一组。合并时只需要把一个树根挂到另一个树根上即可。
如下图所示，若要合并左侧两个组，只需把一个组的树根挂到另一个组的树根上

但这样在实际使用时效率会十分低下。因为树可能会退化成一条链，那么每次找根都需要遍历整条链。如下图所示：

如何解决这个问题呢？路径压缩的并查集登场了，为了加快查找速度，查找时将x到根节点路径上的所有点的parent都设为根节点，该优化方法称为压缩路径。即将上图中的链式结构转化为如下的结构，叶子结点都直接与根相连：

路径压缩的并查集中的查找操作算法如下：

int find(int x){//返回x所在树的根，同时把从x到根的所有节点都直接挂到根上。
	if(x == fa[x]) {
		return x; //如果当前就是根，直接返回
	}
	return fa[x] = find(fa[x]); //否则，先把fa[x]置为树根，再返回树根
}

这是个巧妙的递归函数，可以返回x所在树的根，同时把从x到根的所有节点都直接挂到根上。可以用之前所述的链式结构模拟一下递归过程帮助理解。

问题：

思路：

题目看起来是动态的，每个地点的犯人每一秒都会移动到另一个地点，如果直接根据题意去模拟，将变得十分复杂。注意到哨站存在的时间是无限长的，那么在某地设置了哨站，所有现在或未来经过这个地点的犯人都会被捕，相当于等着犯人送人头。另外犯人在每个地点都只会向某一个地点转移，也就是说每个点都只有一个出边，再换句话说，每个节点都只有一个父亲，在没有成环的情况下，节点就会构成一棵棵的树(森林），因此我们在树根设置哨站是最划算的。这正好符合并查集的结构，我们可以使用并查集进行求解。成环的话，我们在环的任意一个点设置即可，因为其他点一定会经过这个点。
那么如何找出这些树的树根，以及选出犯人数最多的m个树根呢？我们可以使用并查集进行维护，同时，用另一个数组num维护集合大小即可。

我们使用set[]数组表示并查集，set[i]的值表示i所属组的树根。在初始时，set[i] = i，每个元素都自成一组。使用num[]数组表示组中的犯人数，num[i]的值表示以i为树根的组中的犯人数，初始时即为每个结点的初始犯人数。
我们可以边读取每个结点的父节点边构建并查集和更新num[]数组，逐渐将每个组中的犯人全部集中到树根中。在读取第i个结点的父节点后，我们需要判断是否需要将第i个结点所属的组和其父节点所属的组合并。若第i个结点所属组的树根与其父节点所属组的树根相同，则不需要合并。若不同，则需要合并，设第i个结点所属组的树根为tmpParent，第i个结点的父节点为parent，我们先将第i个结点所属组的树根设为其父节点的树根，即set[i] = find(parent)，然后再更新num[]数组，我们既然已经合并了两个组，那么原来i所属组的犯人数应全转移到其父节点所属组，即num[find(parent)] += num[tmpParent];num[tmpParent] = 0。
对于不成环的情况，经过这一系列操作，每个组中的犯人数集结在组的根节点，即num[root]，而其他结点的犯人数为0，即num[node] = 0。对于成环的情况，我们也并不需要特殊处理，最后犯人会集结在环中我们遍历的最后一个结点上。举个例子：若环为5——>6——>7——>5，我们从小到大遍历，7为遍历的最后一个元素，其所属组的树根为它自己，它的父节点为5，5所属组的树根暂时为6，当调用路径压缩的查找算法去判断7所属组的树根是否等于5所属组的树根时，5所属组的树根将会更新为7（由于6的父节点为7），即不需要合并。而此时num[7]已经是环中的总犯人数了，因为在遍历6时，就已经将5、6中的犯人全转移到了7中，加上7中初始的犯人数，即为环中犯人总数。即最后环中犯人数集结在环中最后遍历的结点上，而其他结点的犯人数为0。
最后将num[]数组排序，累加最大的m个数即为答案

代码：

import java.util.*;

public class Main {
    static int[] set = new int[100002];
    static int[] num = new int[100002];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, m, i, parent, tmpParent;
        long ans = 0;
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (i = 1;i <= n;i++) {
            set[i] = i;
            num[i] = scanner.nextInt();
        }
        for (i = 1;i <= n;i++) {
            parent = scanner.nextInt();
            if (findAndUnion(i) != findAndUnion(parent)) {
                tmpParent = findAndUnion(i);
                set[i] = findAndUnion(parent);
                num[findAndUnion(parent)] += num[tmpParent];
                num[tmpParent] = 0;
            }
        }
        Arrays.sort(num);
        for (i = 1;i <= m && 100002 - i >= 0;i++) {
            ans += num[100002 - i];
        }
        System.out.println(ans);

    }

    static int findAndUnion(int node) {
        if (set[node] == node) {
            return node;
        }
        return set[node] = findAndUnion(set[node]);
    }

}