@yavinci Just another improvement to your path compression union find algorithm, add weight to each root in the tree. When only use path compression, the time complexity is (N + MlogN), with weighted quick union path compression the time complexity will be (N + M)*lgN. M is the number is unions in the array, and N is the number of nodes.

public int countComponents(int n, int[][] edges) { if (null == edges || 0 == edges.length) return n; // build root array int[] roots = new int[n]; // build size array (add weight to the tree) int[] size = new int[n]; for (int i = 0; i < n; i ++) roots[i] = i; Arrays.fill(size, 1); // for each edge, change its root to its parant for (int i = 0; i < edges.length; i ++) { // for the nodes in each edge, use path compression to let it pointed to its root int root1 = find(roots, edges[i][0]); int root2 = find(roots, edges[i][1]); if (root1 != root2) { if (size[root1] < size[root2]) { roots[root1] = root2; size[root1] += size[root2]; } else { roots[root2] = root1; size[root2] = size[root1]; } n --; } } return n; } private int find(int[] roots, int node) { while (roots[node] != node) { roots[node] = roots[roots[node]]; node = roots[node]; } return node; }Number of Connected Components in an Undirected Graph