集合合并

[编程题]集合合并

热度指数：2537 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定若干个32位int数字集合，每个集合中的数字无重复，譬如：
{1,2,3} {2,5,6} {8}
将其中交集不为空的集合合并，保证合并完成后所有集合之间无交集，输出合并后的集合个数以及最大集合中元素的个数。

输入描述:

输入格式：
1. 第一行为一个数字N，表示集合数。
2. 接下来N行，每行一个非空集合，包含若干个数字，数字之间用空格分开。
假设第i个集合的大小为Si，数据满足N<=100000,ΣSi<=500000

输出描述:

输出格式：
1. 第一行为合并后的集合个数。
2. 第二个为最大集合中元素的个数。

示例1

输入

输出

2
5

算法知识视频讲解

Java

pein531

思路很简单，使用并查集来求解。当然，并查集常用的优化套路全都要用上，如：路径压缩、根据rank进行合并。但是在本题的数据量下，老老实实读完数据然后构建并查集是过不了的！必须一边读数据一边构建并查集，同时还要一边做集合的合并，才能勉强AC！

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            int n = Integer.parseInt(line);
            UnionFind uf = new UnionFind();
            // 边读取数据边对并查集中的元素进行合并
            for(int i = 0; i < n; i++){
                String[] str = br.readLine().split(" ");
                int[] set = new int[str.length];
                for(int j = 0; j < set.length; j++){
                    set[j] = Integer.parseInt(str[j]);
                    uf.add(set[j]);
                    if(j > 0) {
                        uf.union(set[j], set[j - 1]);     // 合并集合
                    }
                }
            }
            // 获得连通分量数
            System.out.println(uf.getCount());
            // 获得最大连通分量大小
            System.out.println(uf.getMaxSize());
        }
    }
}

class UnionFind {
    int count;        // 连通分量数
    int maxSize;      // 最大集合的规模
    private HashMap<Integer, Integer> parent;       // 节点->根
    private HashMap<Integer, Integer> rank;         // 节点->树的大小
    public UnionFind(){
        parent = new HashMap<Integer, Integer>();
        rank = new HashMap<Integer, Integer>();
        maxSize = 1;
    }
    
    public void add(int num) {
        if(!parent.containsKey(num)){
            parent.put(num, num);
            rank.put(num, 1);
            count++;
        }
    }
    
    private int find(int x){
        int root = x;
        while(parent.get(root) != root){
            root = parent.get(root);
        }
        // 把沿途节点的根都修改为father
        while(x != root){
            int temp = parent.get(x);
            parent.put(x, root);
            x = temp;
        }
        return root;
    }

    public void union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY){
            return;
        }
        int rankX = rank.get(rootX);
        int rankY = rank.get(rootY);
        if(rankX < rankY){
            parent.put(rootX, rootY);      // y的树高就将x合并到y
            rank.put(rootY, rankX + rankY);
            maxSize = Math.max(maxSize, rank.get(rootY));
        }else{
            // 高度相等时随便合并，但是树的最大高度会增加
            parent.put(rootY, rootX);
            rank.put(rootX, rankX + rankY);
            maxSize = Math.max(maxSize, rank.get(rootX));
        }
        count--;
    }
    
    public int getCount(){
        return count;
    }
    
    public int getMaxSize(){
        return maxSize;
    }
}

发表于 2022-01-06 15:24:52 回复(0)

Java

奥奇笑

import java.util.Scanner;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class UF {
    int maxCount;    // 最大集合的元素个数
    int count;    // 集合个数
    HashMap<Integer, Integer> parent; // value 是 key 所在集合的根节点
    HashMap<Integer, Integer> counter; // value 是 key 所在集合的元素个数
    public UF() {
        count = 0;
        maxCount = 0;
        parent = new HashMap<Integer, Integer>();
        counter = new HashMap<Integer, Integer>();
    }
    public int count() {
        return count;
    }
    public int maxCount() {
        return maxCount;
    }
    public int find(int p) {
        int root = p;
        while (root != parent.get(root)) {
            root = parent.get(root);
        }
        // 路径压缩
        while (p != root) {
            int temp = parent.get(p);
            parent.put(p, root);
            p = temp;
        }
        return root;
    }
    
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;
        if (counter.get(i) < counter.get(j)) {
            parent.put(i, j);
            counter.put(j, counter.get(j) + counter.get(i));
            if (maxCount < counter.get(j)) maxCount = counter.get(j);
        } else {
            parent.put(j, i);
            counter.put(i, counter.get(i) + counter.get(j));
            if (maxCount < counter.get(i)) maxCount  = counter.get(i);
        }
        count--;
    }
}

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        List<int[]> list = new ArrayList<>();
        UF uf = new UF();
        while (sc.hasNextLine()) {
            String[] strs = sc.nextLine().trim().split(" ");
            int[] nums = new int[strs.length];
            for (int i = 0; i < nums.length; i++) {
                nums[i] = Integer.valueOf(strs[i]);
                if (!uf.parent.containsKey(nums[i])) {
                    uf.parent.put(nums[i], nums[i]);
                    uf.counter.put(nums[i], 1);
                    uf.count++;
                }
            }
            int p = nums[0];
            for (int i = 1; i < nums.length; i++) {
                list.add(new int[] {p, nums[i]});
            }
        }
        for (int[] pair : list) {
            uf.union(pair[0], pair[1]);
        }
        System.out.println(uf.count);
        System.out.println(uf.maxCount);
    }
}

求助各位大佬们，我这个代码case通过率是66.67%，超时了，不知道怎么优化了