# Java DFS & Union Find

• Similar to 200.number of islands [https://leetcode.com/problems/number-of-islands/#/description](link url) this problem has two solutions:
DFS:

``````public class Solution {
public int findCircleNum(int[][] M) {
int N = M.length, count = 0;
boolean[] visited = new boolean[N];
for(int i = 0;i < N;i++){
if(!visited[i]){
count++;
dfs(i, N, visited, M);
}
}
return count;
}
private void dfs(int i, int N, boolean[] visited, int[][] M){
visited[i] = true;
for(int j = 0;j < N;j++){
if(M[i][j] == 1 && !visited[j]){
dfs(j, N, visited, M);
}
}
}
}
``````

UnionFind:

``````public class Solution {
public int findCircleNum(int[][] M) {
int N = M.length, count = N;
int[] root = new int[N];
for(int i = 0;i < N;i++){
root[i] = i;
}
//remember we don't need to process duplicated edges
for(int i = 0;i < N;i++){
for(int j = i + 1;j < N;j++){
if(M[i][j] == 1){
int idi = findRoot(i, root), idj = findRoot(j, root);
if(idi != idj){
root[idi] = idj;
count--;
}
}
}
}
return count;
}
int findRoot(int id, int[] root){
while(id != root[id]){
root[id] = root[root[id]];
id = root[id];
}
return id;
}
}
``````

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