# 并查集

并查集一般用于：

1. 将两个集合合并
2.  询问两个元素是否在一个集合当中

    基本原理：

每个集合用一棵树来表示。

树根的编号就是整个集合的编号。

每个节点存储他的父节点，使用pre\[x]表示x的父节点

问题：

1. 如何判断树根？答 if pre\[x] == x
2. 如何求x的集合编号？答 while pre\[x] != x: x = pre\[x]
3. 如何合并两个集合？答 如何需要合并的两个集合为a、b，那么将b插入到a中即可（或将a插入b中）即pre\[b]=a

优化：

1. 路径压缩（常用）：从某个节点a找到其所在集合的根节点r，那么可以将a到根节点路径上各点x直接指向根节点，即使得pre\[x] = r
2. 按秩合并（不常用）：对于每个集合有一个rank值，在合并两个集合的时候将rank值较小的插入到rank值较大的中

## 模版题：合并集合

![image-20200712220313785](https://122767808-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MBDSdFU2kWrJocOCeSH%2Fsync%2F5d5fac0f6fa89004f61465556b4d2d351c2242a4.png?generation=1594602037587424\&alt=media)

```python
N = 100010

p = [0] * N


# 查找根节点，并进行路径优化
def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


if __name__ == '__main__':
    n, m = [int(c) for c in input().split()]
    for i in range(1, n + 1):
        p[i] = i

    for _ in range(m):
        op, a, b = [c for c in input().split()]
        a, b = int(a), int(b)
        if op == "M":
            # 将a插入到b中
            p[find(a)] = find(b)
        else:
            if find(a) == find(b):
                print("Yes")
            else:
                print("No")

"""
IN：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
OUT：
Yes
No
Yes
"""
```

## 维护元素个数：连通块中点的数量

![image-20200712222053278](https://122767808-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MBDSdFU2kWrJocOCeSH%2Fsync%2F4cf772f67a3522153df771b7e6f3343bbedbf8a7.png?generation=1594602036584367\&alt=media)

注意：连通块中的点指的是两点之间是连通的，比如从点a可以访问到点b，从点b可以访问到点a，那么a、b两点之间就是连通的，是连通块中的点。

```python
N = 100010

p = [0] * N
cnt = [1] * N


# 查找根节点，并进行路径优化
def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


if __name__ == '__main__':
    n, m = [int(c) for c in input().split()]
    for i in range(1, n + 1):
        p[i] = i

    for _ in range(m):
        recv = input().split(" ")
        op = recv[0]
        if op == "C":
            a, b = int(recv[1]), int(recv[2])
            a = find(a)
            b = find(b)
            if a != b:
                # 将a插入到节点b中
                p[a] = b
                # 维护根节点连通块中的数量
                cnt[b] += a
        elif op == "Q1":
            a, b = int(recv[1]), int(recv[2])
            if find(a) == find(b):
                print("Yes")
            else:
                print("No")
        else:
            a = int(recv[1])
            print(cnt[find(a)])

"""
IN:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
OUT:
Yes
2
3
"""
```

## Python并查集模版

### 普通版

```python
class DSU(object):

    def __init__(self, n):
        # n代表点的个数
        self.pre = [0] * n
        for i in range(n):
            self.pre[i] = i

    # 查找x的根节点
    def find(self, x: int):
        while self.pre[x] != x:
            x = self.pre[x]
        return x

    # 合并两个集合
    # False: 说明已经在一个集合中，无需合并
    # True: 合并成功
    def union(self, a: int, b: int) -> bool:
        ar = self.find(a)
        br = self.find(b)
        if ar == br:
            return False

        # 将a所在集合插入到b所在集合中
        self.pre[ar] = br
        return True


if __name__ == '__main__':
    # 存在环CASE
    # edges = [
    #     (0, 1), (1, 2), (1, 3),
    #     (2, 4), (3, 4), (2, 5)
    # ]
    # 不存在环CASE
    edges = [
        (0, 1), (1, 2), (1, 3),
        (3, 4), (2, 5)
    ]
    n = 6
    dsu = DSU(n)
    for a, b in edges:
        if not dsu.union(a, b):
            raise print("存在环")

    print("不存在环")
```

### 按秩合并

```python
class DSU(object):

    def __init__(self, n):
        # n代表点的个数
        self.pre = [0] * n
        for i in range(n):
            self.pre[i] = i

        # rank表示每个集合的高度
        self.rank = [0] * n

    # 查找x的根节点
    def find(self, x: int):
        while self.pre[x] != x:
            x = self.pre[x]
        return x

    # 合并两个集合
    # False: 说明已经在一个集合中，无需合并
    # True: 合并成功
    def union(self, a: int, b: int) -> bool:
        ar = self.find(a)
        br = self.find(b)
        if ar == br:
            return False

        if self.rank[ar] > self.rank[br]:
            self.pre[br] = ar
        elif self.rank[ar] < self.rank[br]:
            self.pre[ar] = br
        else:
            self.pre[ar] = br
            self.rank[br] += 1
        return True


if __name__ == '__main__':
    # 存在环CASE
    # edges = [
    #     (0, 1), (1, 2), (1, 3),
    #     (2, 4), (3, 4), (2, 5)
    # ]
    # 不存在环CASE
    edges = [
        (0, 1), (1, 2), (1, 3),
        (3, 4), (2, 5)
    ]
    n = 6
    dsu = DSU(n)
    for a, b in edges:
        if not dsu.union(a, b):
            raise print("存在环")

    print("不存在环")
```

### 路径压缩

```python
class DSU(object):

    def __init__(self, n):
        # n代表点的个数
        self.pre = [0] * n
        for i in range(n):
            self.pre[i] = i

    # 查找x的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
    # 如 self.pre = [-1] * n，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
    def find(self, x: int):
        if self.pre[x] != x:
            self.pre[x] = self.find(self.pre[x])
        return self.pre[x]

    # 合并两个集合
    # False: 说明已经在一个集合中，无需合并
    # True: 合并成功
    def union(self, a: int, b: int) -> bool:
        ar = self.find(a)
        br = self.find(b)
        if ar == br:
            return False

        # 将a所在集合插入到b所在集合中
        self.pre[ar] = br
        return True


if __name__ == '__main__':
    # 存在环CASE
    # edges = [
    #     (0, 1), (1, 2), (1, 3),
    #     (2, 4), (3, 4), (2, 5)
    # ]
    # 不存在环CASE
    edges = [
        (0, 1), (1, 2), (1, 3),
        (3, 4), (2, 5)
    ]
    n = 6
    dsu = DSU(n)
    for a, b in edges:
        if not dsu.union(a, b):
            raise print("存在环")

    print("不存在环")
```

## 练习

### [684. 冗余连接](https://leetcode-cn.com/problems/redundant-connection/)

```python
from typing import List


class DSU(object):

    def __init__(self, n):
        # n代表点的个数
        self.pre = [0] * n
        for i in range(n):
            self.pre[i] = i

    # 查找x的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
    # 如 self.pre = [-1] * n，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
    def find(self, x: int):
        if self.pre[x] != x:
            self.pre[x] = self.find(self.pre[x])
        return self.pre[x]

    # 合并两个集合
    # False: 说明已经在一个集合中，无需合并
    # True: 合并成功
    def union(self, a: int, b: int) -> bool:
        ar = self.find(a)
        br = self.find(b)
        if ar == br:
            return False

        # 将a所在集合插入到b所在集合中
        self.pre[ar] = br
        return True


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        dsu = DSU(1010)
        for a, b in edges:
            if not dsu.union(a, b):
                if a > b:
                    return [b, a]
                return [a, b]
        return []
```

### [685. 冗余连接 II](https://leetcode-cn.com/problems/redundant-connection-ii/)

```python
from typing import List
from collections import defaultdict


class DSU(object):

    def __init__(self, n):
        # n代表点的个数
        self.pre = [0] * n
        for i in range(n):
            self.pre[i] = i

    # 查找x的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
    # 如 self.pre = [-1] * n，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
    def find(self, x: int):
        if self.pre[x] != x:
            self.pre[x] = self.find(self.pre[x])
        return self.pre[x]

    # 合并两个集合
    # False: 说明已经在一个集合中，无需合并
    # True: 合并成功
    def union(self, a: int, b: int) -> bool:
        ar = self.find(a)
        br = self.find(b)
        if ar == br:
            return False

        # 将a所在集合插入到b所在集合中
        self.pre[ar] = br
        return True


class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        """
        先判断有没有入度为 2 的点：
        没有入度为 2 的点：则一定有首尾相接的圈（意思是箭头方向全是一致，全是顺时针或者逆时针），
        此时可以按照无向图的情形处理，删除最后出现的多余的边。
        有入度为 2 的点 c，两条边先后出现的顺序是 [a,c] 和 [b,c]：在边集中去掉 [b,c]，
        判断剩下的边集中是否存在圈： a. 如果存在圈，则删掉 [a,c]。 b. 不存在圈，则删掉 [b,c].
        """
        dd = defaultdict(list)

        flag = False
        # 找到入度为2的点
        for a, b in edges:
            dd[b].append(a)
            if len(dd[b]) == 2:
                flag = True
                break

        # 选择其中一组移除 （list(dd[b])[0], b）
        if flag:
            dsu = DSU(1010)
            for a, c in edges:
                if a == dd[b][1] and c == b:
                    continue
                dsu.union(a, c)

            if not dsu.union(dd[b][1], b):
                return [dd[b][1], b]
            else:
                return [dd[b][0], b]

        dsu = DSU(1010)
        for a, c in edges:
            if not dsu.union(a, c):
                return [a, c]
        return list()
```

## 参考

[【图解】遇到就深究——并查集](https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/tu-jie-yu-dao-jiu-shen-jiu-bing-cha-ji-by-chun-men/)

[并查集总结](https://github.com/Liu821218213/LeetCode-Orust/blob/master/%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%80%BB%E7%BB%93.md)
