Leetcode——唯唯诺诺对并查集的初次相见

雨点打透心脏的1/2处 2023-01-10 15:57 102阅读 0赞

# 基本概念 #

*  并查集是一种数据结构
 *  并查集这三个字，一个字代表一个意思。
 *  并（Union），代表合并
 *  查（Find），代表查找
 *  集（Set），代表这是一个以字典为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素
 *  并查集的典型应用是有关连通分量的问题
 *  并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)O(1)

# 并查集的实现 #

## 数据结构 ##

并查集跟树有些类似，只不过她跟树是相反的。在树这个数据结构里面，每个节点会记录它的子节点。在并查集里，每个节点会记录它的父节点。

class UnionFind:
    
        def __init__(self):
            """
            记录每个节点的父节点
            """
            self.father = {}

## 初始化 ##

当把一个新节点添加到并查集中，它的父节点应该为空

def add(self,x):
            """
            添加新节点
            """
            if x not in self.father:
                self.father[x] = None

## 合并两个节点 ##

如果发现两个节点是连通的，那么就要把他们合并，也就是他们的祖先是相同的。这里究竟把谁当做父节点一般是没有区别的。

def merge(self,x,y,val):
            """
            合并两个节点
            """
            root_x,root_y = self.find(x),self.find(y)
            
            if root_x != root_y:
                self.father[root_x] = root_y

## 两节点是否连通 ##

def is_connected(self,x,y):
            """
            判断两节点是否相连
            """
            return self.find(x) == self.find(y)

## 查找祖先 ##

def find(self,x):
            """
            查找根节点
            """
            root = x
    
            while self.father[root] != None:
                root = self.father[root]
    
            return root

### 这里有一个优化的点：如果我们树很深，比如说退化成链表，那么每次查询的效率都会非常低。所以我们要做一下路径压缩。也就是把树的深度固定为二。 ###

### 这么做可行的原因是，并查集只是记录了节点之间的连通关系，而节点相互连通只需要有一个相同的祖先就可以了。 ###

## 路径压缩 ##

def find(self,x):
            """
            查找根节点
            路径压缩
            """
            root = x
    
            while self.father[root] != None:
                root = self.father[root]
    
            # 路径压缩
            while x != root:
                original_father = self.father[x]
                self.father[x] = root
                x = original_father
             
            return root

# 牛刀小试 #

[直通车][Link 1]

class Solution:
        def findCircleNum(self, isConnected: List[List[int]]) -> int:
            def find(index: int) -> int:
                if parent[index] != index:
                    parent[index] = find(parent[index])
                return parent[index]
    
            def union(index1: int, index2: int):
                parent[find(index1)] = find(index2)
    
            provinces = len(isConnected)
            parent = list(range(provinces))
    
            for i in range(provinces):
                for j in range(i + 1, provinces):
                    if isConnected[i][j] == 1:
                        union(i, j)
    
            circles = sum(parent[i] == i for i in range(provinces))
            return circles

[以上笔记参考：][Link 2]

[Link 1]: https://leetcode-cn.com/problems/number-of-provinces/solution/
[Link 2]: https://leetcode-cn.com/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/