啥是并查集（Union-find set）

并查集是用于合并集合的一种树形的逻辑数据结构，实际上底层通过【数组】实现。它只能合并集合，不能分割集合

并查集要解决的问题

解决【需要通过某个元素查找该元素所在的集合】的问题
当需要【通过某个元素查找该元素所在的集合】时，我们有什么办法呢？首先一个，可以给每个元素带上一个属性，该属性标记该元素归属于哪个集合；另外一个，我们可以把【通过属性记录集合所属关系的方式优化成根据元素搜索集合的根root】，就是并查集方法。

并查集算法思想

每个集合内部应该按照树形结构组织，这样每个集合就是一棵树，就可以由树根root唯一代表，所有集合就组成一片森林。例如，每个公司就是个树形的集合，根root就是老板，马云可以拿出来代表阿里集合，Pony可以代表腾讯集合。如果我们想合并两个集合，只需要将一个root作为另一个root的孩子即可，这就是树形结构的优势。具体步骤如下：

• 1.每个元素自成一个集合，每个元素本身就是root
• 2.集合合并时，集合根结点间重新形成上下级关系即可

并查集由一个数组或者字典father和两个方法findroot()和union()构成
father记录每个点的父节点，如 num_a = father[num_b]，表示num_a是num_b的father
函数findroot()接收一个num，查找这个num所在集合的根爸爸；
union()接收两个num（num_A, num_B），查找num_A, num_B所在集合的根爸爸，通过根爸爸相连实现两个集合的union

代码模板

class UnionFindSet:
    def __init__(self, father=[]):
        self.father = father
        

    # 查找并返回ele所在集合的根爸爸root
    def findRoot(self, ele):
        root = ele
        
        # 当自己不是自己的father，说明就还不是root，继续向上搜索集合树
        while root != self.father[root]:
            root = self.father[root]
        return root
    
    # 合并两个集合
    def union(self, ele1, ele2):
    
        # 分别查找两个元素所在集合的根爸爸root
        root1 = self.findRoot(ele1)
        root2 = self.findRoot(ele2)
        
        # 如果两个元素不在同一集合，则合并两个集合
        if root1 != root2:
            self.father[root1] = root2

优化：
我们已经知道每个集合是一棵树。对于集合中的元素ele，要查找所在集合的root，必须层层向上查找，查找次数为树的高度。极端情况下，如果树只存在一条路径，则退化成了线性查找。显然的思路是，我们让每棵集合树变得尽可能矮胖，最矮矮到什么层度？2层高的树，不能再矮了

并查集压缩树高度

于是，我们在findRoot中做一些优化，利用递归将整个查找路径上的所有元素的father都修改为root：

# 查找并返回ele所在集合的根爸爸root
    def findRoot(self, ele):
        # 利用递归不断更新一条路径上的father，并减小了集合内树的高度
        if self.father[ele] != ele:
            self.father[ele] = self.findRoot(self.father[ele])    
        return self.father[ele] 

于是，并查集类的代码模板如下：

class UnionFindSet:
    def __init__(self, father=[]):
        self.father = father
        
    # 查找并返回ele所在集合的根爸爸root
    def findRoot(self, ele):
        # 利用递归不断更新一条路径上的father，并减小了集合内树的高度
        if self.father[ele] != ele:
            self.father[ele] = self.findRoot(self.father[ele])    
        return self.father[ele]
    
    # 合并两个集合
    def union(self, ele1, ele2):
        # 分别查找两个元素所在集合的根爸爸root
        root1 = self.findRoot(ele1)
        root2 = self.findRoot(ele2)
        
        # 如果两个元素不在同一集合，则合并两个集合
        if root1 != root2:
            self.father[root1] = root2

并查集的应用

leetcode990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以满足所有给定的方程时才返回 true，否则返回 false。

分析：
题目中存在两种表达式，分别描述等量关系和不等量关系。我们可以先利用等量关系，将相等的元素划分入同一个集合内；集合建设完毕后，再通过不等关系，检查是否和集合自相矛盾，以判断全体式子是否能够被满足。

思路：
首先处理所有等式，将相等的元素纳入同一集合，需要查找等式中元素归属的集合进行集合合并，因此可以选择给元素带上归属属性，也可以通过并查集实现

• 通过设置属性查找归属集合的代码

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        # 考虑将相等元素放入一个集合中
        # 【先将equations排序，==在前，!=在后。先处理相等的情况，划分好集合，此时只负责建好集合，不判断是否合法；然后再处理不等关系，通过不等关系判断建好的集合是否valid。】
        equations.sort(key=lambda x: x[1:3], reverse=True)
        # print(equations)
        l = len(equations)
        # 每个元素归属集合的属性，通过字典记录
        varies_to_set_Dict = dict()
        set_no = 0
        for i in range(l):
            # 处理每一个表达式

            exp = equations[i]
            ele1, ele2, ops = exp[0], exp[-1], exp[1:3]

            # 如果两个变量都出现在已有集合中
            if ele1 in varies_to_set_Dict and ele2 in varies_to_set_Dict:
                # 将ele1和ele2所在的两个集合合并，归到最先产生的集合上，即set_no小的集合上
                if ops == '==':
                    s1, s2 = varies_to_set_Dict[ele1], varies_to_set_Dict[ele2]
                    if s1 < s2:
                        # s2集合中的元素迁移到s1，实现合并
                        for set_ele in locals()[s2]:
                            varies_to_set_Dict[set_ele] = s1
                    else:
                        # s1集合中的元素迁移到s2，实现合并
                        for set_ele in locals()[s1]:
                            varies_to_set_Dict[set_ele] = s2
                else:
                    if varies_to_set_Dict[ele1] == varies_to_set_Dict[ele2]:
                        return False
            # 如果两个变量都没出现在已有集合中，创建集合并纳入元素
            elif ele1 not in varies_to_set_Dict and ele2 not in varies_to_set_Dict:
                if ops == '==':
                    set_name = 'set_%s' % str(set_no)
                    locals()[set_name] = set()
                    locals()[set_name].add(ele1)
                    locals()[set_name].add(ele2)
                    set_no += 1
                    # 登记所属集合的标记
                    varies_to_set_Dict[ele1] = set_name
                    varies_to_set_Dict[ele2] = set_name
                else:
                    if ele1 == ele2:
                        return False
                    set_name = 'set_%s' % str(set_no)
                    locals()[set_name] = set()
                    locals()[set_name].add(ele1)
                    # 登记所属集合的标记
                    varies_to_set_Dict[ele1] = set_name
                    set_no += 1
                    set_name = 'set_%s' % str(set_no)
                    locals()[set_name] = set()
                    locals()[set_name].add(ele2)
                    # 登记所属集合的标记
                    varies_to_set_Dict[ele2] = set_name
                    set_no += 1
            # 只有一个变量出现在已有集合中
            else:
                # 只关注相等关系
                if ops == '==':
                    if ele1 in varies_to_set_Dict:
                        varies_to_set_Dict[ele2] = varies_to_set_Dict[ele1]
                        locals()[varies_to_set_Dict[ele2]].add(ele2)
                    else:
                        varies_to_set_Dict[ele1] = varies_to_set_Dict[ele2]    
                        locals()[varies_to_set_Dict[ele1]].add(ele1)
            # print(varies_to_set_Dict)
        return True

• 通过并查集查找归属集合的代码

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        # 考虑将相等元素放入一个集合中
        # 【先将equations排序，==在前，!=在后。先处理相等的情况，划分好集合，此时只负责建好集合，不判断是否合法；然后再处理不等关系，通过不等关系判断建好的集合是否valid。】
        equations.sort(key=lambda x: x[1:3], reverse=True)
        # print(equations)
        l = len(equations)
        father = dict()
        ufs = UnionFindSet(father)
        for i in range(l):
            # 处理每一个表达式

            exp = equations[i]
            ele1, ele2, ops = exp[0], exp[-1], exp[1:3]
            # 找集合根
            r1, r2 = ufs.findRoot(ele1), ufs.findRoot(ele2)
            if ops == '==':
                # 合并
                ufs.union(r1, r2)
            else:
                if r1 == r2:
                    return False
                
        return True

class UnionFindSet:
    def __init__(self, father=dict()):
        self.father = father
        

    # 查找并返回ele所在集合的根爸爸root
    def findRoot(self, ele):
        root = ele
        
        # 如果ele没有father，自己做自己的father，返回
        if root not in self.father:
            self.father[root] = root
            return root
        
        # 当自己不是自己的father，说明就还不是root，继续沿路径向上搜索
        if root != self.father[root]:
            self.father[root] = self.findRoot(self.father[root])
        return self.father[root]
    
    # 合并两个集合
    def union(self, ele1, ele2):
        # 分别查找两个元素所在集合的根爸爸root
        root1 = self.findRoot(ele1)
        root2 = self.findRoot(ele2)
        
        # 如果两个元素不在同一集合，则合并两个集合
        if root1 != root2:
            self.father[root1] = root2

leetcode #### 785. 判断二分图
本题的切入点在于，node i 与 graph[i]的任一元素不在同一集合，而graph[i]内的全部元素在同一集合。期间涉及到集合的合并，这里提供本人使用并查集的golang版本答案

//// 实现并查集 ////

type UFS struct {
    father_slice []int
}
// findRoot和union方法绑定UFS struct

// 查找node在并查集中的root
func (ufs UFS) findRoot(node int) int {
    if ufs.father_slice[node] != node {
        // 让node的father直接指向根root
        ufs.father_slice[node] = ufs.findRoot(ufs.father_slice[node])
    }
    return ufs.father_slice[node]
}

// union合并
func (ufs UFS) union(node1, node2 int) {
    node1_root, node2_root := ufs.findRoot(node1), ufs.findRoot(node2)
    if node1_root != node2_root {
        // root2做root1的小弟
        ufs.father_slice[node2_root] = node1_root
    }
}

//// 实现并查集 ////

func isBipartite(graph [][]int) bool {
    ufs := UFS{make([]int, len(graph))}
    for i := 0; i < len(graph); i ++ {
        ufs.father_slice[i] = i
    }

    // 每个i与graph[i]属于互斥集合
    for i := 0; i < len(graph); i ++ {
        // i与graph[i]的元素v属于一个集合，false
        for _, v := range graph[i] {
            if ufs.findRoot(i) == ufs.findRoot(v) {
                return false
            }
        }
        
        // 否则，graph[i]元素合并
        if len(graph[i]) > 0 {
            first_ele := graph[i][0]
            for j := 1; j < len(graph[i]); j ++ {
                ufs.union(first_ele, graph[i][j])
            }
        }
    }
    fmt.Println(ufs.father_slice)
    return true
}