给定若干个32位int数字集合,每个集合中的数字无重复,譬如:
{1,2,3} {2,5,6} {8}
将其中交集不为空的集合合并,保证合并完成后所有集合之间无交集,输出合并后的集合个数以及最大集合中元素的个数。
输入格式:
1. 第一行为一个数字N,表示集合数。
2. 接下来N行,每行一个非空集合,包含若干个数字,数字之间用空格分开。
假设第i个集合的大小为Si,数据满足N<=100000,ΣSi<=500000
输出格式:
1. 第一行为合并后的集合个数。
2. 第二个为最大集合中元素的个数。
3 1 2 3 2 5 6 8
2 5
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; } }
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); } }