leetcode-并查集

并查集(Disjoint-Set)是一种可以动态维护若干个不重叠的集合，并支持合并与查询两种操作的一种数据结构。

在leetcode的等式方程的可满足性了解到并查集的相关知识，可以学习一下B站教程并查集。

并查集是一种树形数据结构，主要用于相交集合的合并和查询，例如在图中判断某些顶点是否在同一个连通分量中，或者判断图中是否存在环。

¶主要操作

初始化：以数组为例，设置parent数组用于记录当前下标位置对应元素其父节点的下标，例如，parent[i]=j表示j是i的父节点，初始化parent数组，通常初始化值为下标值或者某一固定值；
查找操作：查找某一元素x的根节点，递归的查找x对应的parent数组的值，直到parent中的值为初始化值；
合并操作，对于两个元素x和y，首先查找其各自根节点，如果根节点相同，则说明二者在同一分类中，无须进行合并，反之说明二者不在一个分支中，需要进行合并，默认的合并方式是将任意一个元素的父节点设置为另一个元素即可。
优化：
- 如果存在长度为n的链式结构，则在查找根节点的过程中需要遍历n个元素。将链式结构进行路径压缩，其根节点作为根节点，其余n-1个元素均为子节点，则查找过程只需要遍历一个元素即可。
- 在合并过程中，如果x所在分支深度为Dx，y所在分支深度为Dy，则需要比较二者大小，将深度小的连接到深度大的分支上，最终的分支深度不会超过max（Dx，Dy），引入表示秩的数组rank[]用于记录每个元素距离根节点的深度。

代码如下：

public class test {
    static int vertices = 6;
    /*
        初始化parent和rank
     */
    static void initialise(int parent[], int rank[]){
        for(int i=0; i<vertices; i++){
            parent[i] = -1;
            rank[i] = 0;
        }
    }
    /*
        查找x的根节点
     */
    static int find_root(int x, int parent[]){
        int x_root = x;
        while(parent[x_root] != -1){
            x_root = parent[x_root];
        }
        return x_root;
    }
    /*
        根据rank合并两个节点
        如果x y的根节点相同，则说明在同一个分支中，无须合并
        如果不相同，将分支层数小的合并到层数大的分支上
     */
    static int union_vertices(int x, int y, int parent[],int rank[]){
        int x_root = find_root(x,parent);
        int y_root = find_root(y,parent);
        if(x_root == y_root){
            return 0;
        }else{
            if(rank[x_root] > rank[y_root]){
                parent[y_root] = x_root;
            }else if(rank[y_root] > rank[x_root]){
                parent[x_root] = y_root;
            }else {
                parent[x_root] = y_root;
                rank[y_root]++;
            }
            return 1;
        }
    }
    public static void main(String[] args) {
        int[] parent = new int[vertices];
        int[] rank = new int[vertices];
        int edge[][]={
            {0,1},{1,2},{1,3},{2,4},{3,4},{2,5}
        };
        initialise(parent,rank);
        for(int i=0; i<6; i++){
            int x = edge[i][0];
            int y = edge[i][1];
            if(union_vertices(x,y,parent,rank) == 0){
                System.out.println("cycle");
                return;
            }
        }
        System.out.println("no cycle");
    }
}

¶leetcode题解

class Solution {
    public boolean equationsPossible(String[] equations) {
        //使用并查集，对6个字母进行合并查找
        int length = equations.length;
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        // ==两边的字母进行合并，表示在一个集合中
        for (String str : equations) {
            if (str.charAt(1) == '=') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                union(parent, index1, index2);
            }
        }
        // !=两边的字母，查找其各自的根节点，如果相等，说明这两个字母的值相等，这与!=矛盾，直接返回false
        for (String str : equations) {
            if (str.charAt(1) == '!') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                if (find(parent, index1) == find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }
// 直接合并两个分支，不考虑秩以及在同一分支的情况
// 在同一分支直接合并，与初始化的parent[i]=i一样
    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index) {
        while (parent[index] != index) {
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
}