# simple, short, intuitive java dfs solution + union find

• simple dfs solution

``````public int countComponents(int n, int[][] edges) {
if(n <= 1) return n;
HashMap<Integer, List<Integer>> graph = new HashMap<>();
HashSet<Integer> visited = new HashSet<Integer>(); //nodes in set means they are not visited
for(int i=0;i<n;i++) { //initiate graph
graph.put(i, new ArrayList<Integer>());
visited.add(i);
}
for(int i=0;i<edges.length;i++){ //build graph
graph.get(edges[i][0]).add(edges[i][1]);
graph.get(edges[i][1]).add(edges[i][0]);
}
int result = 0;
while(visited.size()>0){ //if visited.size()>0, there are unvisited nodes
result++;
dfs(graph, visited.iterator().next(), visited);
}
return result;
}
private void dfs(HashMap<Integer, List<Integer>> graph, int node, HashSet<Integer> visited){
if(visited.contains(node)) visited.remove(node);
else return;
for(int i=0;i<graph.get(node).size();i++){
dfs(graph, graph.get(node).get(i), visited);
}
}
``````

union-find solution

``````public int countComponents(int n, int[][] edges) {
int[] parent = new int[n];
Arrays.fill(parent, -1);
for(int i=0;i<edges.length;i++){
int x = find(parent, edges[i][0]);
int y = find(parent, edges[i][1]);
if(x != y)
union(parent, x, y);
}
int neg1num = 0;
for(int i=0;i<n;i++){
if(parent[i] == -1) neg1num++;
}
return neg1num;
}
private int find(int[] parent, int v){
while(parent[v] != -1) v = parent[v];
return v;
}
private void union(int[] parent, int v1, int v2){
int v1Set = find(parent, v1);
int v2Set = find(parent, v2);
parent[v1Set] = v2Set;
}
``````

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