圖論基礎

并查集

• 并查集，總的來說，操作分為三步初始化(每一個節點的父親是自己)，定義union(index1,index2)函數，定義find(index)函數

并查集詳細內容博客

習題

聯盟X

聯盟X

• 典型的求解連通分支的題目，這個題目求解的最小連通分支
• 我們采用并查集進行求解

import os
import sys
from collections import defaultdict# 請在此輸入您的代碼# 并查集的問題
n, m = map(int, input().split())
# 記錄父親節點
parent = list(range(n + 1))
def find(index1):if parent[index1] != index1:parent[index1] = find(parent[index1])return parent[index1]def union(index1, index2):# parent[index1] = find(parent[index2])parent[find(index1)] = find(index2)for _ in range(m):u, v = map(int, input().split())union(u, v)# 根據祖先計數，也就是同一個并查集的放在一起
store = defaultdict(int)
for i in range(1, n + 1):fa = find(i)store[fa] += 1
print(min(store.values()))

藍橋幼兒園

藍橋幼兒園

• 典型的并查集模版題目

import os
import sys# 請在此輸入您的代碼# 典型的并查集問題N,M = map(int,input().split())
parent = list(range(N+1))def find(index):if parent[index] != index:parent[index] = find(parent[index])return parent[index]def union(index1,index2):parent[find(index1)] = find(index2)for _ in range(M):op,x,y = map(int,input().split())if op == 1:union(x,y)if op == 2:if find(x)==find(y):print("YES")else:print("NO")