并查集—数组实现

前言

给一堆不重复的元素分组，判别两个元素是否在同一组中，可以使用并查集数据结构。并查集的实现可以用数组，链表，树。这里我们用最简单的数组。

题目

用例

在知道并查集之前，我想到的是用ArrayList数组，元素类型为HashSet，每一组就对应一个HashSet，再来一张HashMap，类似于一张成员组号表，成员是key，组号是value。在Map里查询：
1.没查到，创建新HashSet，添加新组；
2.查到一个，就把另一个加入查到的组；
3.都查到但是组别不一样，就合并组别。

这样一来可以解题，但是所用的数据结构以及代码都过于冗杂。我的解答就不做参考，直接看标准解答。

解答

并查集

我们常常说数据结构与算法，他们的关系可以看作 ：好的数据结构可以简化算法。接下来用数组来实现并查集。

并查集可以看作每一组都有严格的等级制度，一个组内有大组长，小组长，组员等等。判断一个人在哪一组只需要从下往上找找到组长即可。

例如有五个人，初始化五个人分别代表五个组，然后2加入1组（认一组组长1做组长），3加入2所在组。

现在问3在哪一组，就可以通过索引层层往上，直到索引index和value相等。

arr[3]是2，arr[2]是1，arr[1]是1，OK查找完毕，3和1是一组的。这个过程的逻辑其实是一个嵌套。而且在已知3是1组后，就可以把arr[3]的value改为1，下次查找的时候更快，减少时间复杂度，因为嵌套的特性，这一组的value都会被改为1。

属性一个数组即可
方法查找根结点；合并组别；

查找根结点

int[] fa;

public UnionFindSet(int n){
    this.fa = new int[n];
    for (int i=0;i<n;i++) {
    	this.fa[i] = i;
}

public int find(int x){
	return this.find(this.fa[x]);
}

如果不加限制条件，达到根结点后会一直嵌套，内存泄漏。应当添加判断是否到达根节点：

public int find(int x){
	if (this.fa[x] != x) {
		return this.find(this.fa[x]);
	}
	return x;
}

其实就是到达根节点this.fa[x] == x直接返回，不再嵌套。

但这还没有压缩路径，我们需要把每次找到的父级value赋给子级value

public int find(int x){
    if(this.fa[x] != x) {
        return this.fa[x] = this.find(this.fa[x]);
    }
    return x;
}

有了find函数，组合函数和整套代码就变得小菜一碟。

如果x,y的value不等，选x的组长作为合并组的组长。y的组长投靠x的组长即可。

public void union(int x,int y){
    int x_fa = this.find(x);
    int y_fa = this.find(y);
    if(x_fa != y_fa) {
        this.fa[y_fa] = x_fa;
    }
}

写好并查集这个数据结构，按照题目要求写逻辑即可。

输入

这道题不可输入输出写在一个循环里，否则可能造成输入一行，输出一行，不满足题目要求。此时我们可以先用二维数组把输入的abc保存下来。

Scanner sc = new Scanner(System.in);
int n = sc.nextInt(),m = sc.nextInt();
int[][] inputs = new int[m][3];
for (int i=0;i<m;i++) {
    inputs[i][0] = sc.nextInt();
    inputs[i][1] = sc.nextInt();
    inputs[i][2] = sc.nextInt();
}

int a = 0,b = 0, c = 0;
UnionFindSet union = new UnionFindSet(n+1);
for (int i=0;i<m;i++) {
    a = inputs[i][0];
    b = inputs[i][1];
    c = inputs[i][2];

    int teamIndexA = union.find(a);
    int teamIndexB = union.find(b);
    if (c != 0 && c!= 1 || a < 1||b<1||a>n||b>n) {
        System.out.println("da pian zi");
    }
    else if (c == 0) {
        if (teamIndexA != teamIndexB) {
            union.union(a,b);
        }
    } else if (c == 1){
        if (teamIndexA == teamIndexB) {
            System.out.println("we are a team");
        } else {
            System.out.println("we are not a team");
        }
    }

优化

我将判断输入是否合法以及判断如何输出放在了一个if里面，可以分开，增加代码的可读性和可维护性。并且判断不合法后，continue进入下一次循环，防止出现数组下标越界访问等不可控问题。

打印we are a team或者not a team时，由于只有两种选项，可以用三目表达式。

            if (c != 0 && c!= 1 || a < 1||b<1||a>n||b>n) {
                System.out.println("da pian zi");
                continue;
            }
            if (c == 0) {
                if (teamIndexA != teamIndexB) {
                    union.union(a,b);
                }
            } else if (c == 1){

                System.out.println(teamIndexA==teamIndexB?"we are a team":"we are not a team");

//                if (teamIndexA == teamIndexB) {
//                    System.out.println("we are a team");
//                } else {
//                    System.out.println("we are not a team");
//                }
            }