Friend Circles – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem – Friend Circles – Leetcode Challenge – Java Solution.
Source – qiyuangong’s repository.
public class Solution {
public void dfs(int[][] M, int[] visited, int i) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && visited[j] == 0) {
visited[j] = 1;
dfs(M, visited, j);
}
}
}
public int findCircleNum(int[][] M) {
// DFS
int[] visited = new int[M.length];
int count = 0;
for (int i = 0; i < M.length; i++) {
if (visited[i] == 0) {
dfs(M, visited, i);
count++;
}
}
return count;
}
/*public int findCircleNum(int[][] M) {
// BFS
int[] visited = new int[M.length];
int count = 0;
Queue < Integer > queue = new LinkedList < > ();
for (int i = 0; i < M.length; i++) {
if (visited[i] == 0) {
queue.add(i);
while (!queue.isEmpty()) {
int s = queue.remove();
visited[s] = 1;
for (int j = 0; j < M.length; j++) {
if (M[s][j] == 1 && visited[j] == 0)
queue.add(j);
}
}
count++;
}
}
return count;
}*/
/*
// Union find
int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
if (xset != yset)
parent[xset] = yset;
}
public int findCircleNum(int[][] M) {
int[] parent = new int[M.length];
Arrays.fill(parent, -1);
for (int i = 0; i < M.length; i++) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && i != j) {
union(parent, i, j);
}
}
}
int count = 0;
for (int i = 0; i < parent.length; i++) {
if (parent[i] == -1)
count++;
}
return count;
}*/
}
