如何降低无向图连通分量计算的时间复杂度？

问题描述 #

这是一个模拟社交网络用户连接的无向图问题：

• 包含编号1到N的N个节点
• 边由from数组和to数组表示
• Task数组中的每个元素为需要查询其所在连通分量大小的节点编号

示例 #

N = 5
From = [2,2,1,1]
To = [1,3,3,4]
Task = [4,2,5]

答案：

[4,4,1]

解释：
节点4和节点2所在的连通分量包含4个节点，节点5所在的连通分量仅包含自身，因此结果为[4,4,1]

约束条件 #

N=2 to 10^5
size of arrays from, to, and tasks is 2 to 10^5

原代码使用BFS逐个查询节点所在连通分量大小，在大输入下超时，需要优化时间复杂度。

原代码问题分析 #

原代码每次查询都对目标节点做一次BFS遍历，时间复杂度为O(T*(N+E))，当T（任务数）和N都达到1e5量级时，重复遍历同一连通分量会导致大量冗余计算，直接触发超时。

优化方案：使用并查集（Union-Find） #

并查集是专门处理连通性问题的数据结构，通过路径压缩和按秩合并优化后，初始化、合并、查询操作的时间复杂度几乎为O(1)（均摊时间复杂度），完美适配大规模数据场景。

核心思路 #

1. 初始化两个数组：
   • parent[]：记录每个节点的父节点，初始时每个节点的父节点是自身
   • size[]：记录每个连通分量的大小，初始时每个分量大小为1
2. 遍历所有边，对每条边的两个节点执行合并操作，将小分量合并到大分量上，同时更新分量大小
3. 处理每个查询任务时，只需找到目标节点的根节点，直接返回对应size数组的值即可

优化后的Java代码 #

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static int[] parent;
    private static int[] size;

    public static List<Integer> solve(int N, List<Integer> from, List<Integer> to, List<Integer> tasks) {
        // 初始化并查集
        parent = new int[N + 1]; // 节点编号从1到N
        size = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        // 合并所有边的节点
        int edgeCount = from.size();
        for (int i = 0; i < edgeCount; i++) {
            int u = from.get(i);
            int v = to.get(i);
            union(u, v);
        }

        // 处理查询任务
        List<Integer> result = new ArrayList<>();
        for (int node : tasks) {
            int root = find(node);
            result.add(size[root]);
        }
        return result;
    }

    // 查找根节点，带路径压缩
    private static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩，直接指向根节点
        }
        return parent[x];
    }

    // 合并两个节点所在的连通分量，按秩（大小）合并
    private static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return; // 已经在同一分量，无需合并
        }
        // 把小分量合并到大分量上
        if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }
}

优化效果说明 #

• 初始化阶段：O(N)
• 合并所有边：O(E α(N))，α是阿克曼函数的反函数，增长极慢，几乎可视为常数
• 查询所有任务：O(T α(N))
  整体时间复杂度为O(N + E + T)，完全适配1e5量级的输入规模，不会出现超时问题。

内容的提问来源于stack exchange，提问作者Learner