#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2021/7/30 23:12
# @Author  : @linlianqin
# @Site    : 
# @File    : 并查集專題（合并、查找、集合）.py
# @Software: PyCharm
# @description:'''
并查集其實就是多個數組，每一個數組都是一顆樹，然后并查集相當于是一個森林
基本操作：
合并（union)
查找（find）
集合（set)
'''# 初始化：給定一系列升序連續的編號，將編號初始化為并查集，形成一個森林,每個元素的父親結點（根節點）都是自己
def UFS_init(n):father = [i for i in range(n)]root = [i for i in range(n)]return father,root# 查找：在已經有的并查集中查找給定的元素的根節點——即通過self,father來進行查找根節點
def UFS_findroot(element,n,father):# 找到根節點時，返回根節點if element == father[element]:return element# 沒有找到則繼續查找return UFS_findroot(father[element],n,father)# 進行路徑壓縮
def UFS_ZIP(element,father,root):# 臨時保存當前元素temp = element# 查找element的根節點while element != father[element]:element = father[element]# 將路徑壓縮while temp != father[temp]:root[temp] = elementtemp = father[temp]return element# 查找：在已經有的并查集中查找給定的元素的根節點——路徑壓縮，即通過self.root來進行查找根節點，時間復雜度為O（1)
def UFS_findrootzip(element,root):return root[element]# 合并：
## 當兩個元素不在同一個集合的時候合并兩個集合，即將其中一個集合的根節點指向另一個集合的根節點即可合并
## 當兩個元素在同一個集合的時候不進行操作
def UFS_union(x,y,n,father,root):### 判斷兩個元素是否在同一個集合的方法是判斷兩個元素的根節點是否為同一個，是則在同一個集合，否則不是rootx = UFS_findroot(x,n,father)rooty = UFS_findroot(y,n,father)if rootx != rooty:root[rooty] = rootx # 將x的根節點設置為yfather[rooty] = rootx # 將x的父節點設置為yreturn root,father# 假設有編號0-10的同學
# 其中兩個人為一組，一個人可以出現在多個二人組合中，問可以分為幾個大組
# 輸入：人數n(用于創建一定空間的父節點數組和根節點數組），組別m(用于合并同一組的人）
# 如輸入：
# n = 11 , m = 6
# groups = [[0,1,2],[2,3,4],[4,6],[5,7],[8,9],[9,10]]
# 輸出：
# group_num = 3 _____ 【0,1,2,3,4,6】【8,9,10】def main(m,n,groups):# 大組的個數其實就是并查集中不同根節點的個數isroot = [0 for _ in range(n)]# 初始化并查集father,root = UFS_init(n)print("初始化：")print("father:",father)print("root:",root)# 遍歷組別，合并同一組別的兩個集合for group in groups:for index in range(len(group)-1):UFS_union(group[index],group[index+1],n,father,root)print("合并后：")print("father:",father)print("root:",root)# 遍歷self.root，查看有多少個不同的集合個數for i in range(n):isroot[root[i]] = 1print("isroot:", isroot)num_group = sum(isroot)return num_groupn = 11
m = 6
groups = [[0,1,2],[2,3,4],[4,5,6],[5,7],[8,9],[9,10]]
print(main(m,n,groups))## 其他
# todo:統計每個集合的元素個數——將isroot[root[i]] = 1改為isroot[root[i]] += 1
# todo:答應出合并集合后的最終狀態——遍歷所有元素，res = [[] for _ in range(n],將元素對應添加到根節點作為索引的對應小列表中即可

運行結果：

初始化：
father: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
root: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
合并后：
father: [0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8]
root: [0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8]
isroot: [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
2