并查集

并查集一般用于：

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

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

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

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并查集模版

普通版

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("不存在环")

按秩合并

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("不存在环")

路径压缩

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. 冗余连接

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

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()

参考

【图解】遇到就深究——并查集

并查集总结