T27351:01最小生成树

补图连通分量, http://cs101.openjudge.cn/practice/27351/

30937:01最小生成树 (new data)

http://cs101.openjudge.cn/practice/30937/

给定一张 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。

一个优雅且高效的解决方案是利用补图的连通分量数来求解。

解题思路

本题给定了一个完全图，其中包含 $m$ 条边权为 1 的边，其余边权均为 0。我们需要求该图的最小生成树（MST）的边权和。由于我们希望最小生成树的边权和最小，因此应当尽可能多地使用边权为 0 的边。

设仅由 0 权边构成的图为 $G_{0}$ 。

如果 $G_{0}$ 包含 $C$ 个连通分量，我们可以通过添加 $C - 1$ 条 1 权边将这 $C$ 个连通分量连接起来，形成一棵生成树。
因此，最小生成树的边权和即为 $C - 1$ 。
这里的 $G_{0}$ 实际上就是由 1 权边构成的图 $G_{1}$ 的补图（Complement Graph）。问题转化为求 $G_{1}$ 补图的连通分量个数。

python

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)

使用并查集（Union-Find）实现的高效优化版本。

思路：基于连通块大小的并查集

在补图中，如果节点 $i$ 与某个连通块 $C$ 之间没有完全重合的边（即原图中 $i$ 到 $C$ 的边数小于 $C$ 的大小 $| C |$ ），则说明在补图中 $i$ 至少与 $C$ 中的一个节点相连。因此，我们可以在补图中将 $i$ 与该连通块合并。

通过维护当前所有连通块的根节点集合 active_roots，我们只需在遍历每个节点 $i$ 时：

统计 $i$ 到各个连通块的边数。
遍历 active_roots，若 $i$ 到某连通块的边数 $< 该连通块大小$ ，则进行并查集合并。

时间复杂度证明：虽然看似有两层循环，但对于节点 $i$ ，未发生合并的连通块数量不会超过 $i$ 的度数 $d e g (i)$ ；而发生合并的次数在整个算法运行期间最多只有 $N - 1$ 次。因此，整体时间复杂度为 $O (N α (N) + M)$ ，其中 $α$ 为阿克曼反函数，效率极高。

python

import sys

def solve():
    # 使用快速输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 初始化原图邻接表
    adj = [[] for _ in range(n)]
    idx = 2
    for _ in range(m):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        adj[u].append(v)
        adj[v].append(u)
        idx += 2
        
    # 并查集数组：parent 记录父节点，sz 记录连通块大小
    parent = list(range(n))
    sz = [1] * n
    
    # 并查集查找（迭代版路径压缩，避免递归栈溢出）
    def find(i):
        path = []
        while parent[i] != i:
            path.append(i)
            i = parent[i]
        for node in path:
            parent[node] = i
        return i

    # 并查集合并（按秩合并）
    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            # 将小树合并到大树上
            if sz[root_i] < sz[root_j]:
                root_i, root_j = root_j, root_i
            parent[root_j] = root_i
            sz[root_i] += sz[root_j]
            return root_i, root_j  # 返回合并后的根和被合并的根
        return None

    # 记录当前所有活跃的连通块根节点
    active_roots = set(range(n))
    
    for i in range(n):
        # 统计节点 i 在原图中到各个连通块的边数
        comp_edge_count = {}
        for neighbor in adj[i]:
            root = find(neighbor)
            comp_edge_count[root] = comp_edge_count.get(root, 0) + 1
        
        root_i = find(i)
        to_union = []
        
        # 遍历所有活跃的连通块
        for root in active_roots:
            if root == root_i:
                continue
            # 若原图中 i 到该连通块的边数小于该连通块的总大小
            # 则说明补图中 i 与该连通块至少有一条边相连，可以合并
            if comp_edge_count.get(root, 0) < sz[root]:
                to_union.append(root)
        
        # 执行合并操作，并更新活跃根节点集合
        for root in to_union:
            res = union(i, root)
            if res:
                winner, loser = res
                active_roots.discard(loser)  # 移除已被合并的根

    # 最终剩余的连通块数量
    ans = len(active_roots) - 1
    print(ans)

if __name__ == '__main__':
    solve()

T27351:01最小生成树 ​

T27351:01最小生成树