My Union Find Solution in Java

• The idea is very straightforward: When a union operation is successful, the number of connected components decrease by one.

``````public class Solution {
public int countComponents(int n, int[][] edges) {
//use this map to find the representative of each component
Map<Integer, Integer> mymap = new HashMap<Integer, Integer>();
//make disjoint sets
for (int i = 0; i < n; i++) {
mymap.put(i, i);
}
int num_components = n;
//union sets
for (int i = 0; i < edges.length; i++) {
int x = edges[i][0];
int y = edges[i][1];
if (union(x, y, mymap) == true){
//a union operation is successfull, one less component
num_components--;
}
}
return num_components;
}
//find the representative
public int find(int key, Map<Integer, Integer> mymap) {
int value = mymap.get(key);
if (value == key) {
return value;
}
return find(value, mymap);
}

public boolean union(int x, int y, Map<Integer, Integer> mymap) {
int xRoot = find(x, mymap);
int yRoot = find(y, mymap);
if (xRoot == yRoot) {
return false;
}
//union
mymap.put(yRoot, xRoot);
return true;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.