模板：

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for _ in range(n)]
        self.count = n
    def find(self,p):
        while self.parent[p] != self.parent[self.parent[p]]:
            self.parent[p] = self.parent[self.parent[p]]
        return self.parent[p]
    def union(self,p,q):
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        if self.rank [i] < self.rank [j]:
            self.parent[i] = j
            self.rank [j] += self.rank [i]
        else:
            self.parent[j] = i
            self.rank [i] += self.rank [j]
        self.count -= 1

并查集unionfind：

能够解决朋友圈，岛屿等问题。
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
并查集有三种基本操作，获得根节点，判断两节点是否连通，以及将两不连通的节点相连（相当于将两节点各自的集合合并）·

获得根节点
```
def get_root(self, i)
```
判断两节点是否联通
```
def is_connected(self, i, j)
```

不连通的节点相连

def union(self, i, j)

1.1 初始化

class Solution:
  def __init__(self, n):
      self.parent = list(range(n))

1.2 获得根节点

由于parent[i]仅表示自己的直接父节点，查询两个节点是否相交需要比较它们的根节点是否相同。因此要封装一个查询自己根节点的方法。

def get_root(self, i):
  while i != self.parent[i]:
      i = self.parent[i]
  return i

当前每次执行get_root时，需要一层一层的找到自己的父节点，很费时。由于根节点没有父节点，并且文章开始处提到过如果一个节点没有父节点，那么它的父节点就是自己，因此可以说只有根节点的父节点是自己本身。现在我们加上一个判断，判断当前节点的父节点是否为根节点，如果不为根节点，就递归地将自己的父节点设置为根节点，最后返回自己的父节点。

def get_root(self, i):
  if self.parent[i] != self.parent[self.parent[i]]:
      self.parent[i] = self.get_root(self.parent[i])
  return self.parent[i]

1.3 比较根节点是否相同来判断两节点是否连通。

def is_connected(self, i, j):
  return self.get_root(i) == self.get_root(j)

1.4 当要连通两个节点时，我们要将其中一个节点的根节点的parent，设置为另一个节点的根节点。

注意，连通两个节点并非仅仅让两节点自身相连，实际上是让它们所属的集合实现合并。

def union(self, i, j):
  i_root = self.get_root(i)
  j_root = self.get_root(j)
  self.parent[i_root] = j_root

由于调用get_root时需要通过不断找自己的直接父节点，来寻找根节点，如果这棵树的层级过深，会导致性能受到严重影响。因此我们需要在union时，尽可能的减小合并后的树的高度。
因此，当合并树时，分别获得节点i和节点j的root i_root和j_root之后，我们通过访问rank[i_root]和rank[j_root]来比较两棵树的高度，将高度较小的那棵连到高度较高的那棵上。如果高度相等，则可以随便，并将rank值加一。

def union(self, i, j):
  i_root = self.get_root(i)
  j_root = self.get_root(j)
  if self.rank[i_root] == self.rank[j_root]:
      self.parent[i_root] = j_root
      self.rank[j_root] += 1
  elif self.rank[i_root] > self.rank[j_root]:
      self.parent[j_root] = i_root
  else:
      self.parent[i_root] = j_root

例1. pyq任务：

只给你朋友圈的矩阵，返回朋友圈数量 ```python class DisjointSet: def init(self,n):

  ## 初始化parent和rank
  self.parent = [i for i in range(n)]
  self.rank = [1 for _ in range(n)]
  self.count = n

def find(self,p):

  ### 找到root
  while self.parent[p] != self.parent[self.parent[p]]:
      self.parent[p] = self.parent[self.parent[p]]
  return self.parent[p]

def union(self,p,q):

  ### 首先，p和q一定是领边的
  ## 先找到p，q的爹
  i = self.find(p)
  j = self.find(q)
  # 如果p，q的爹一样，说明在同一个union里面
  if i == j:
      return
  #如果p，q的爹不一样，p的爹和q的爹比较rank，让p or q都接在大的rank上
  # 更新接完后爹的rank
  # 做一次不同爹更新意味着少了一个union，count-1
  if self.rank [i] < self.rank [j]:
      self.parent[i] = j
      self.rank [j] += self.rank [i]
  else:
      self.parent[j] = i
      self.rank [i] += self.rank [j]
  self.count -= 1

主函数，就不写在class Solution里面了

def findCircleNum( M): “”” :type M: List[List[int]] :rtype: int “”” disjoint_set = DisjointSet(len(M)) for i in range(len(M)): for j in range(i+1,len(M)): if M[i][j] == 1 : disjoint_set.union(i,j) return disjoint_set.count

if name == ‘main‘: M=[[1,1,0],[1,1,0],[0,0,1] M=[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] disjoint_set.count=findCircleNum(M) print(disjoint_set) print(‘num of pyq:’, disjoint_set.count)

<a name="YgJh1"></a>
## 例2. 岛问题
```python
class DisjointSet:
    def __init__(self,n):
        ## 初始化parent和rank
        self.parent = [i for i in range(n+1)]
        self.rank = [1 for _ in range(n)]
        self.rank.append(3)
        self.count = n
    def find(self,p):
        ### 找到root
        while self.parent[p] != self.parent[self.parent[p]]:
            self.parent[p] = self.parent[self.parent[p]]
        return self.parent[p]
    def union(self,p,q):
        ### 首先，p和q一定是领边的
        ## 先找到p，q的爹
        i = self.find(p)
        j = self.find(q)
        # 如果p，q的爹一样，说明在同一个union里面
        if i == j:
            return
        #如果p，q的爹不一样，p的爹和q的爹比较rank，让p or q都接在大的rank上
        # 更新接完后爹的rank
        if self.rank [i] < self.rank [j]:
            self.parent[i] = j
            self.rank [j] += self.rank [i]
        else:
            self.parent[j] = i
            self.rank [i] += self.rank [j]
        self.count -= 1
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n=len(grid)
        if n==0:return 0
        m=len(grid[0])
        num_node= n*m
        def get_index(i,j):
            return i*m+j
        island= DisjointSet(num_node)
        for i in range(n):
            for j in range(m):
                if grid[i][j]=="0":
                    island.union(get_index(i,j),num_node)               
                else:
                    if i>0 and grid[i-1][j]=="1"  :
                        island.union(get_index(i,j),get_index(i-1,j))
                    if  j>0 and grid[i][j-1]=="1" :
                        island.union(get_index(i,j),get_index(i,j-1))
        return island.count

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿完全由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为「封闭岛屿」。
请返回封闭岛屿的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-closed-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class unionfind():
    def __init__(self,num):
        self.parent=[i for i in range(num)]
        self.rank=[1 for _ in range(num)]
        self.rank[-1]=2
        self.count=num
    def find(self,p):
        if self.parent[p]!= self.parent[self.parent[p]]:
            self.parent[p]=self.parent[self.parent[p]]
        return self.parent[p]
    def is_connected(self,p,q):
        return self.find(p)==self.find(q)
    def union(self,p,q):
        i=self.find(p)
        j=self.find(q)
        if i==j:
            return 
        else:
            if self.rank[i]<self.rank[j]:
                self.parent[i]=j
                self.rank[j] +=self.rank[i]
            else:
                self.parent[j]=i
                self.rank[i]+=self.rank[j]
        self.count -=1
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        n=len(grid)
        if n==0: return 0
        m=len(grid[0])
        uf=unionfind(n*m+1)
        def get_index(h,k):
            return h*m+k
        for i in range(n):
            for j in range(m):
                if i==0 or j==0 or i==n-1 or j==m-1:
                    uf.union(get_index(i,j), n*m )
                if grid[i][j]==0:
                    if i+1<n and grid[i+1][j]==0:
                        uf.union(get_index(i,j), get_index(i+1,j) )
                    if j+1<m and grid[i][j+1]==0:
                        uf.union(get_index(i,j), get_index(i,j+1) )
                    if i>0 and grid[i-1][j]==0:
                        uf.union(get_index(i,j), get_index(i-1,j) )
                    if j>0 and grid[i][j-1]==0:
                        uf.union(get_index(i,j), get_index(i,j-1) )
                if grid[i][j]==1:
                    uf.union(get_index(i,j), n*m )
        for i,p in enumerate(uf.parent):
            uf.parent[i]=uf.find(uf.parent[i])
        #print(uf.parent)
        return len(set(uf.parent))-1

算法

并查集Unionfind

模板：