547.Friend Circles

1-DFS

Time complexity :O(n^2)O(n​2​​). The complete matrix of sizen^2n​2​​is traversed

    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) {
        int[] visited = new int[M.length];
        int cnt = 0;
        for(int i = 0; i < M.length; i++){
            if(visited[i] == 0){
                dfs(M, visited, i);
                cnt++;
            }
        }
        return cnt;
    }
}

2-BFS O(n^2)

class Solution {
    public int findCircleNum(int[][] M) {
        int n = M.length;
        int[] visited = new int[n];
        Queue<Integer> q = new LinkedList<>();
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(visited[i] == 0){
                q.offer(i);
                while(!q.isEmpty()){
                    int j = q.poll();
                    visited[j] = 1;
                    for(int k = 0; k < n; k++){
                        if(visited[k] == 0 && M[j][k] == 1){
                            q.offer(k);
                        }
                    }
                }
                cnt++;
            }
        }
        return cnt;
    }
}

3- Union Find

O(n^3) We traverse over the complete matrix once. Union and find operations take O(n) time in the worst case.

class Solution {
    public int find(int[] parent, int i){
        if(parent[i] == -1){
            return i;
        }
        return find(parent, parent[i]);
    }
    public void union(int[] parent, int i, int j){
        int parentI = find(parent, i);
        int parentJ = find(parent, j);
        if(parentI != parentJ){
            parent[parentI] = parentJ;
        }
    }
    public int findCircleNum(int[][] M) {
        int n = M.length;
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        for(int i=0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i != j && M[i][j] ==  1){
                    union(parent, i, j);
                }
            }
        }
        int cnt = 0;
        for(int i = 0 ; i < n; i++){
            if(parent[i] == -1)
                cnt++;
        }
        return cnt;
    }
}