求社交网络中最大用户连通组规模——算法纠错与优化

给定m行以空格分隔的用户ID对(x,y)，代表用户x关注用户y（类似Facebook/Instagram的关注关系）。若两个组存在共同用户则需合并，例如输入：

1 2
3 4
5 6
1 5

可得到连通组[1,2,5,6]和[3,4]，最大组规模为4。

现有一段Java代码无法正确完成分组，且输入规模可达10^{6条数据，用户ID范围为1~10}5，需要低时间复杂度的正确解法。原代码如下：

public int process(int m, int[][] arr) {
    List<Set<Integer>> list = new ArrayList<>();
    
    int ans = 0;
    for(int i=0; i<m; i++) {
        int x = arr[i][0], y = arr[i][1];
        if(j ==0) { // 未定义变量j，属于笔误
            Set<Integer> set = new HashSet<>();
            list.add(set);
            set.add(x);
            set.add(y);
            ans = 2;
            continue;
        }
        boolean found = false;
        for(Set<Integer> set : list) {
            if(set.contains(x) || set.contains(y)) {
                set.add(x);
                set.add(y);
                ans = Math.max(ans, set.size());
                found = true;
                break;
            }
        }
        if(!found) {
            Set<Integer> set = new HashSet<>();
            list.add(set);
            set.add(x);
            set.add(y);
        }
    }
    return ans;
} 

1. 语法错误：代码中使用了未定义的变量j，正确应该是判断i == 0。
2. 逻辑漏洞：当x和y分属两个不同组时，原代码只会将x/y加入第一个匹配到的组，不会合并这两个组。比如输入1 2、3 4、1 3，原代码会把3加入[1,2]组，但不会合并[1,2]和[3,4]，导致分组结果错误。
3. 性能不足：每次遍历所有集合，最坏情况下时间复杂度为O(m*n)（n为集合数量），面对10^6条数据时会严重超时。

并查集是专门处理动态连通性问题的高效数据结构，核心操作是查找和合并，配合路径压缩和按秩合并优化后，操作时间复杂度近似O(1)，完全适配大规模数据场景。

核心思路 #

• 用数组记录每个用户的父节点，初始时每个用户的父节点是自己。
• 用数组记录每个连通组的大小，初始时每个组大小为1。
• 查找操作：找到用户所在组的根节点，同时压缩路径，减少后续查找的时间。
• 合并操作：将两个用户所在的组合并，把较小的组合并到较大的组下，同时更新组的大小和最大组规模。

Java实现代码 #

public class UnionFind {
    private int[] parent;
    private int[] size;
    private int maxSize;

    // 初始化并查集，用户ID范围1~maxUserId
    public UnionFind(int maxUserId) {
        parent = new int[maxUserId + 1];
        size = new int[maxUserId + 1];
        maxSize = 1;
        for (int i = 1; i <= maxUserId; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 查找根节点，带路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并两个用户所在的组
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return; // 已在同一组，无需合并
        }
        // 按组大小合并，小的组合并到大的组下
        if (size[rootX] < size[rootY]) {
            int temp = rootX;
            rootX = rootY;
            rootY = temp;
        }
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
        maxSize = Math.max(maxSize, size[rootX]);
    }

    // 获取最大组的规模
    public int getMaxSize() {
        return maxSize;
    }
}

// 处理函数
public int process(int m, int[][] arr) {
    final int MAX_USER_ID = 100000; // 用户ID范围1~10^5
    UnionFind uf = new UnionFind(MAX_USER_ID);
    for (int[] pair : arr) {
        uf.union(pair[0], pair[1]);
    }
    return uf.getMaxSize();
}

解法优势 #

• 时间效率：每个查找和合并操作的时间复杂度近似O(1)，处理10^6条数据毫无压力。
• 逻辑正确：能够准确合并所有连通的用户组，不会出现漏合并的情况。
• 空间效率：仅需两个大小为10^5+1的数组，内存占用极低。

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