题解 | #村村通工程#

题目链接

题目描述

某市有 $N$ 个城镇，编号从 $1$ 到 $N$ 。现有一些已建成的道路，每条道路连接两个城镇。市政府的目标是实现“村村通”，即任意两个城镇之间都可以通过道路网络相互到达。请计算最少还需要建设多少条道路才能实现这一目标。

解题思路

这个问题可以抽象成一个图论问题。将 $N$ 个城镇看作图的 $N$ 个顶点，已有的 $M$ 条道路看作图的 $M$ 条边。

目标“任意两个城镇间都可以实现交通”等价于让整个图变为一个连通图。

一个图可以由若干个连通分量组成。在同一个连通分量内，任意两个顶点都是相互连通的。不同连通分量之间的顶点则互不连通。

要想让整个图连通，我们只需要将所有的连通分量连接起来。假设图中有 $k$ 个独立的连通分量，我们只需要 $k-1$ 条新的道路（边）就可以将它们全部连接成一个大的连通分量。例如，我们可以从每个连通分量中任选一个顶点，将它们像链条一样串联起来。

因此，问题的核心就转化为了求解图中连通分量的数量 $k$ 。最终答案就是 $k-1$ 。

并查集 (Union-Find) 是解决这类问题的理想数据结构。其基本思想是：

初始时，将每个城镇都看作一个独立的连通分量（集合）。总共有 $N$ 个连通分量。
遍历每条已有的道路，这条道路连接城镇 $u$ 和 $v$ 。
我们使用 union 操作合并 $u$ 和 $v$ 所在的集合。如果它们原本就在同一个集合中，则说明这条道路没有连接新的区域，连通分量数量不变。如果它们在不同的集合中，union 操作会使这两个集合合并，总的连通分量数量减一。
处理完所有 $M$ 条道路后，剩余的集合数量就是图中连通分量的总数 $k$ 。
最少需要建设的道路数量为 $k-1$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

vector<int> parent;

// 查找x所在集合的根节点（带路径压缩）
int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

// 合并x和y所在的集合
bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        return true; // 合并成功
    }
    return false; // 已在同一集合
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0); // 初始化并查集
        
        int components = n;
        
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            if (unite(u, v)) {
                components--;
            }
        }
        
        cout << components - 1 << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int[] parent;

    // 查找x所在集合的根节点（带路径压缩）
    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合并x和y所在的集合
    private static boolean unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            return true; // 合并成功
        }
        return false; // 已在同一集合
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int m = sc.nextInt();

            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i; // 初始化并查集
            }

            int components = n;

            for (int i = 0; i < m; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                if (unite(u, v)) {
                    components--;
                }
            }

            System.out.println(components - 1);
        }
    }
}

import sys

def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]

def unite(parent, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        parent[root_x] = root_y
        return True
    return False

def solve():
    for line in sys.stdin:
        n, m = map(int, line.split())
        
        parent = list(range(n + 1))
        components = n
        
        for _ in range(m):
            u, v = map(int, sys.stdin.readline().split())
            if unite(parent, u, v):
                components -= 1
        
        print(components - 1)

solve()

算法及复杂度

算法：并查集 (Disjoint Set Union)
时间复杂度： $\mathcal{O}(N + M \cdot \alpha(N))$ ，其中 $N$ 是城镇数， $M$ 是道路数， $\alpha(N)$ 是反阿克曼函数，其增长非常缓慢，在实践中可以看作是一个很小的常数。 $\mathcal{O}(N)$ 用于初始化， $\mathcal{O}(M \cdot \alpha(N))$ 用于处理 $M$ 条道路。
空间复杂度： $\mathcal{O}(N)$ ，用于存储并查集的父节点数组。