题解 | #集合合并#

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500010;

int pre[MAXN], count[MAXN];
int mark[MAXN];
vector<int> sets[MAXN];
map<int, int> mp;

// 初始化并查集
void init() {
    for(int i = 1; i < MAXN; i++) {
        pre[i] = i;
        count[i] = 1;
    }
}

// 查找父节点（路径压缩）
int find(int x) {
    if(x == pre[x]) return x;
    return (pre[x] = find(pre[x]));
}

// 读取一行数据
void readLine(vector<int>& vec) {
    char ch;
    int num = 0;
    while((ch = getchar()) != '\n') {
        if(ch != ' ') {
            num = num * 10 + (ch - '0');
        } else {
            vec.push_back(num);
            num = 0;
        }
    }
    vec.push_back(num);
}

int main() {
    init();
    int N, ret = 0, maxSize = 0;
    scanf("%d", &N);
    getchar();
    
    // 读入数据
    for(int i = 1; i <= N; i++) {
        readLine(sets[i]);
    }
    
    // 离散化处理
    int num = 0;
    for(int i = 1; i <= N; i++) {
        for(int& x: sets[i]) {
            if(mp.count(x) == 0) {
                mp[x] = ++num;
            }
            x = mp[x];
        }
    }
    
    // 合并集合
    for(int i = 1; i <= N; i++) {
        int root = find(sets[i][0]);
        for(int j = 1; j < sets[i].size(); j++) {
            int curr = find(sets[i][j]);
            if(root != curr) {
                pre[curr] = root;
                count[root] += count[curr];
            }
        }
    }
    
    // 统计结果
    for(int i = 1; i <= num; i++) {
        int root = find(i);
        if(!mark[root]) {
            mark[root] = 1;
            ret++;
            maxSize = max(maxSize, count[root]);
        }
    }
    
    cout << ret << endl << maxSize << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int MAXN = 500010;
    static int[] parent = new int[MAXN];
    static int[] count = new int[MAXN];
    static boolean[] mark = new boolean[MAXN];
    
    // 初始化并查集
    static void init() {
        for(int i = 1; i < MAXN; i++) {
            parent[i] = i;
            count[i] = 1;
        }
    }
    
    // 查找父节点
    static int find(int x) {
        if(x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init();
        
        int N = sc.nextInt();
        sc.nextLine();
        
        List<List<Integer>> sets = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        
        // 读入数据并离散化
        int num = 0;
        for(int i = 0; i < N; i++) {
            String[] line = sc.nextLine().split(" ");
            List<Integer> set = new ArrayList<>();
            for(String s : line) {
                int val = Integer.parseInt(s);
                if(!map.containsKey(val)) {
                    map.put(val, ++num);
                }
                set.add(map.get(val));
            }
            sets.add(set);
        }
        
        // 合并集合
        for(List<Integer> set : sets) {
            int root = find(set.get(0));
            for(int i = 1; i < set.size(); i++) {
                int curr = find(set.get(i));
                if(root != curr) {
                    parent[curr] = root;
                    count[root] += count[curr];
                }
            }
        }
        
        // 统计结果
        int result = 0, maxSize = 0;
        for(int i = 1; i <= num; i++) {
            int root = find(i);
            if(!mark[root]) {
                mark[root] = true;
                result++;
                maxSize = Math.max(maxSize, count[root]);
            }
        }
        
        System.out.println(result);
        System.out.println(maxSize);
    }
}

import sys

sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = [1] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[py] = px
            self.count[px] += self.count[py]

# 读取输入
N = int(input())
sets = []
for _ in range(N):
    sets.append(list(map(int, input().split())))

# 离散化处理
num_map = {}
curr_num = 0
for set_i in sets:
    for i, num in enumerate(set_i):
        if num not in num_map:
            num_map[num] = curr_num
            curr_num += 1
        set_i[i] = num_map[num]

# 初始化并查集
uf = UnionFind(curr_num)

# 合并集合
for set_i in sets:
    root = uf.find(set_i[0])
    for i in range(1, len(set_i)):
        uf.union(root, set_i[i])

# 统计结果
mark = set()
result = 0
max_size = 0

for i in range(curr_num):
    root = uf.find(i)
    if root not in mark:
        mark.add(root)
        result += 1
        max_size = max(max_size, uf.count[root])

print(result)
print(max_size)