集合合并

/*
并查集算法
*/
#include <bits/stdc++.h>
using namespace std;

class DisjointSet
{
private:
    std::unordered_map<int, int> parent;
    std::unordered_map<int, int> rank; // 秩

public:
    void add(int x)
    {
        if(parent.find(x) == parent.end()) {
            parent[x] = x;
            rank[x] = 0;
        }
    }
    int find(int x)
    {
        // 查找根节点，并包含路径压缩，提高运行效率
        return x == parent[x] ? x : (parent[x] = find(parent[x]));
    }
    void to_union(int x1, int x2)
    {
        int f1 = find(x1);
        int f2 = find(x2);
        if (f1 == f2) return;
        // 按秩合并，find-union操作最坏的运行时间提高至O(log n)
        if (rank[f1] > rank[f2])
            parent[f2] = f1;
        else {
            parent[f1] = f2;
            if (rank[f1] == rank[f2])
                ++rank[f2];
        }
    }
    void printRes()
    {
        int cnt = 0, len_max;
        map<int, int> set;
        for(auto it = parent.begin(); it != parent.end(); it++) {
            find(it->first);  // 将所有节点到根节点的距离压缩至1步
            if(set.find(it->second) == set.end()) set[it->second] = 0;
            set[it->second]++; // 统计合并后每个集合的大小
            if(it->first == it->second) cnt++; // 当根节点为本身时，集合数加一
        }
        for(auto p = set.begin(); p != set.end(); p++)
            len_max = max(len_max, p->second);
        cout << cnt << endl << len_max << endl;
//        for(auto it = parent.begin(); it != parent.end(); it++) {
//            cout << it->first << " " << it->second << endl;
//        }
    }
};


int main(void)
{
    DisjointSet ans = DisjointSet();
    int n, a, b;
    cin >> n;
    while(n--) {
        scanf("%d", &a);
        ans.add(a);
        while(getchar() != '\n') {
            scanf("%d", &b);
            ans.add(b);
            ans.to_union(a, b);
        }
    }
    ans.printRes();
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<int, int> p;
unordered_map<int, int> cnt;

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int pa, int pb) {
    if(cnt[pa] >= cnt[pb]) {
        p[pb] = p[pa];
        cnt[pa] += cnt[pb];
        cnt[pb] = 0;
    } else {
        p[pa] = p[pb];
        cnt[pb] += cnt[pa];
        cnt[pa] = 0;
    }
}

int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
       int a, b;
       cin >> a;
       if(!p.count(a)) {
           p[a] = a;
           cnt[a] = 1;
       } 
       while(getchar() != '\n') {
           cin >> b;
           if(!p.count(b)) {
               p[b] = find(a);
               cnt[find(a)] ++ ;
           } else {
               int pb = find(b), pa = find(a);
               if(pb != pa) {
                   merge(pb, pa);
               }
           }
       }
    }
    
    int res1 = 0, res2 = 0;
    for(auto v : cnt) {
        if(v.second != 0) {
            res1 ++ ;
            res2 = max(res2, v.second);
        }
    }
    cout << res1 << endl << res2 << endl;
    return 0;
}

有 java ac 过的吗，我已经优化到我的极致了，还是卡 66.67% 超时，我太难了。

我的一些优化：

1. 路径压缩
2. 基于rank合并
3. 动态计算最大值
4. 在一行中合并，采用分治法，复杂度从O(n^2)降为O(nlogn)。

import java.util.*;
public class Main {
    private static Map<Integer, Integer> parent = new HashMap<>();
    private static Map<Integer, Integer> size = new HashMap<>();
    private static Map<Integer, Integer> rank = new HashMap<>();
    private static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.valueOf(sc.nextLine());
        for(int i = 0; i < n; i ++) {
            String[] strs = sc.nextLine().split("\\s+");
            int[] arr = new int[strs.length];
            for(int j = 0; j < strs.length; j ++) {
                Integer num = Integer.valueOf(strs[j]);
                arr[j] = num;
                parent.putIfAbsent(num, num);
                size.putIfAbsent(num, 1);
                rank.putIfAbsent(num, 1);
            }

            unionSet(arr, 0, arr.length - 1);
        }

        int count = 0;
        for(Integer k : parent.keySet()) {
            if(k.equals(parent.get(k))) count ++;
        }

        System.out.println(count);
        System.out.println(max);
    }

    public static int unionSet(int[] arr, int start, int end) {
        if(start >= end) return find(arr[start]);

        int mid = (start + end) >>> 1;
        int leftRoot = unionSet(arr, start, mid);
        int rightRoot = unionSet(arr, mid + 1, end);

        return union(leftRoot, rightRoot);
    }

    public static int find(int x) {
        if(x != parent.get(x)) {
            parent.put(x, find(parent.get(x)));
        }

        return parent.get(x);
    }

    public static int union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return pRoot;

        if(rank.get(pRoot) < rank.get(qRoot)) {
            parent.put(pRoot, qRoot);
            size.put(qRoot, size.get(pRoot) + size.get(qRoot));
            max = Math.max(max, size.get(qRoot));
            return qRoot;
        } else {
            parent.put(qRoot, pRoot);
            size.put(pRoot, size.get(pRoot) + size.get(qRoot));
            max = Math.max(max, size.get(pRoot));
            if(rank.get(pRoot).equals(rank.get(qRoot))) {
                rank.put(pRoot, rank.get(pRoot) + 1);
            }
            return pRoot;
        }
    }
}

 import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        scanner.nextLine();
        Set<Integer>[] set=new HashSet[n];
        for(int i=0;i<n;i++){
            String s=scanner.nextLine();
            set[i]=new HashSet<Integer>();
            String[] str=s.split(" ");
            for(int j=0;j<str.length;j++)
                set[i].add(Integer.parseInt(str[j]));
        }
        int count=n;//记录集合各数
        int max=set[0].size();//记录最大集合里有多少个元素
        int sign;//每一次并集最后一个集合的位置。
        for(int i=0;i<n-1;i++) {
            sign=i;
            if(set[i].isEmpty())
                continue;
            for (int j = i+1; j < n; j++) {
                if (set[j].isEmpty())
                    continue;
                if (compare(set[i],set[j])) {
                    set[i].addAll(set[j]);
                    set[j].clear();
                    count--;
                    sign=j;
                    if (max < set[i].size()) {
                        max = set[i].size();
                    }
                }
            }
            if(sign!=i) {
                set[sign].addAll(set[i]);//换到后面可以把之前没法并集，现在可以并集的集合，并集。
            }
        }
        System.out.println(count);
        System.out.println(max);
    }
    public static boolean compare(Set<Integer> set1,Set<Integer> set2){
        Iterator<Integer> iterator=set2.iterator();
        while(iterator.hasNext()){
            if(set1.contains(iterator.next()))
                return true;
        }
        return false;
    }
}

	

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%，超时了，不知道怎么优化了