T27351:01最小生成树

mst, http://cs101.openjudge.cn/practice/27351/

给定一张 n 个点的完全图. 图中所有边的边权均为 0/1, 且有且仅有 m 条边边权为 1.

求解该完全图的最小生成树, 你只需要输出最小生成树的边权和即可.

输入

第一行两个数字 n, m 表示点数,以及边权为 1 的边数。(m <= min{200000, n(n-1)/2})

接下来 m 行, 一行两个数字 a[i],b[i], 表示连接 a[i],b[i] 的边,其边权为 1(1 <= a[i] < b[i] <= n). 保证输入的边两两不同.

输出

一行一个数字,表示最小生成树的边权和.

样例输入

6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
===========
3 0

样例输出

2
===========
0

提示

Subtask1 (20%): n <= 300。

Subtask2 (80%): n <= 100000。

from collections import deque

n, m = map(int, input().split())
graph1 = [set() for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph1[a].add(b)
    graph1[b].add(a)

unvisited = set(range(1, n+1))
components = 0

while unvisited:
    start = unvisited.pop()
    components += 1
    queue = deque([start])
    while queue:
        u = queue.popleft()
        good = unvisited - graph1[u]  # 所有未访问且与 u 有 0-边的点
        for v in good:
            queue.append(v)
        unvisited -= good

print(components - 1)

并查集方法

import sys
sys.setrecursionlimit((1 << 30) - 1)

# 输入节点数n和边数m
n, m = map(int, input().split())

# 初始化邻接集合（存储每个节点的邻居）
li = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    # 转换为0-based索引
    li[a-1].add(b-1)
    li[b-1].add(a-1)

# 并查集父节点数组初始化
di = list(range(n))
# 连通n个节点需要的最少边数（初始为n-1）
edges = n - 1
# 标记已处理的节点
checked = set()

# 并查集查找函数（带路径压缩）
def fin(i):
    if di[i] != i:
        di[i] = fin(di[i])
    return di[i]

# 并查集合并函数
def union(i, j):
    # 若已连通，返回True；否则合并并返回False
    if fin(i) == fin(j):
        return True
    di[fin(i)] = fin(j)
    return False

# 遍历所有节点处理补图边
for i in range(n):
    if i in checked:
        continue
    checked.add(i)
    # 当前节点的邻居集合
    j = li[i]
    # 补图节点：所有非邻居节点（排除自身）
    for u in set(range(n)) - j:
        # 合并i和u，若合并成功则减少需要的边数
        if not union(i, u):
            edges -= 1
            checked.add(u)
        # 提前终止：已满足连通条件
        if edges == 0:
            print(0)
            exit()

# 输出最终需要补充的边数
print(edges)