并查集理論基礎
并查集主要有兩個功能：
- 將兩個元素添加到一個集合中。
- 判斷兩個元素在不在同一個集合
class UnionFind:def __init__(self, n):"""初始化并查集"""self.n = nself.father = list(range(n)) # 每個節點自己是根self.rank = [1] * n # 每棵樹初始高度為1def find(self, u):"""查找根節點，同時做路徑壓縮"""if self.father[u] != u:self.father[u] = self.find(self.father[u]) # 路徑壓縮return self.father[u]def is_same(self, u, v):"""判斷 u 和 v 是否在同一個集合"""return self.find(u) == self.find(v)def join(self, u, v):"""按秩合并 u 和 v 所在集合"""u_root = self.find(u)v_root = self.find(v)if u_root == v_root:return # 已經在同一個集合# 按秩合并：小樹掛到大樹下面if self.rank[u_root] < self.rank[v_root]:self.father[u_root] = v_rootelif self.rank[u_root] > self.rank[v_root]:self.father[v_root] = u_rootelse:self.father[u_root] = v_rootself.rank[v_root] += 1
1.尋找存在的路徑
主函數邏輯
main函數是程序的執行入口，它負責處理輸入、調用并查集的方法，并輸出結果。它的步驟是：
讀取輸入：一次性讀取所有輸入數據，包括元素的總數
n、操作的次數m，以及所有的合并和查詢數據。初始化并查集：創建一個
UnionFind(n)的實例，準備好處理n個元素。執行合并操作：通過一個循環，讀取
m對元素，并對每一對元素調用uf.union()方法，將它們所在的集合合并。執行查詢：讀取最后需要查詢的一對元素
source和destination。輸出結果：調用
uf.is_same()方法來判斷source和destination是否屬于同一個集合，然后根據結果輸出1或0。
class UnionFind:
? ? #每個人的根都指向自己
? ? def __init__(self, size):
? ? ? ? self.parent = list(range(size+1))
? ? def find(self, u):
? ? ? ? if self.parent[u] != u:
? ? ? ? ? ? self.parent[u] = self.find(self.parent[u]) # 路徑壓縮
? ? ? ? return self.parent[u]
? ? def union(self, u, v):
? ? ? ? root_u = self.find(u)
? ? ? ? root_v = self.find(v)
? ? ? ? if root_u != root_v:
? ? ? ? ? ? self.parent[root_v] = root_u
? ? #檢查兩個元素 u 和 v 是否屬于同一個集合（也就是它們是否“連通”）
? ? def is_same(self, u, v):
? ? ? ? return self.find(u) == self.find(v)
def main():
? ? #sys.stdin.read 這個方法有點不一樣。它是從標準輸入流中一次性讀取所有的輸入
? ? import sys
? ? input = sys.stdin.read
? ? data = input().split()
? ? index = 0
? ? n = int(data[index])
? ? index += 1
? ? m = int(data[index])
? ? uf = UnionFind(n)
? ? index += 1
? ? for _ in range(m):
? ? ? ? s = int(data[index])
? ? ? ? index += 1
? ? ? ? t = int(data[index])
? ? ? ? index += 1
? ? ? ? uf.union(s, t)
? ?
? ? source = int(data[index])
? ? index += 1
? ? destination = int(data[index])
? ? if uf.is_same(source, destination):
? ? ? ? print(1)
? ? else:
? ? ? ? print(-1)
if __name__ == "__main__":
? ? main()
今天就到這里了有點難！
