547. Friend Circles

// LeetCode URL: https://leetcode.com/problems/friend-circles/

/**
 * Using Union Find
 *
 * Time Complexity: O(N^2 * ⍺). Where ⍺ is a very slow growing function, which
 * is always ≤ 4. Thus the time complexity becomes O(N^2).
 *
 * Space Complexity: O(N)
 *
 * N = Number of students in the class.
 */
class Solution1 {

    class UnionFind {
        int[] parent;
        int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int findParent(int n) {
            if (parent[n] != n) {
                parent[n] = findParent(parent[n]);
            }
            return parent[n];
        }

        public boolean union(int a, int b) {
            int pA = findParent(a);
            int pB = findParent(b);

            if (pA == pB) {
                return false;
            }

            if (rank[pA] >= rank[pB]) {
                parent[pB] = pA;
                rank[pA] = rank[pA] == rank[pB] ? rank[pA] + 1 : rank[pA];
            } else {
                parent[pA] = pB;
            }

            return true;
        }
    }

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0) {
            return 0;
        }

        int N = M.length;
        UnionFind uf = new UnionFind(N);
        int count = N;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j || M[i][j] == 0) {
                    continue;
                }
                if (uf.union(i, j)) {
                    count--;
                }
            }
        }

        return count;
    }
}

/**
 * Using DFS
 *
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(N). Visted array Size. Also recursion stack cannot grow
 * more than size N
 *
 * N = Number of strudents in the class.
 */
class Solution2 {
    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0) {
            return 0;
        }

        boolean[] visited = new boolean[M.length];
        int count = 0;

        for (int i = 0; i < M.length; i++) {
            if (!visited[i]) {
                dfsHelper(M, visited, i);
                count++;
            }
        }

        return count;
    }

    public void dfsHelper(int[][] M, boolean[] visited, int i) {
        visited[i] = true;
        for (int j = 0; j < M.length; j++) {
            if (visited[j] || M[i][j] == 0) {
                continue;
            }
            dfsHelper(M, visited, j);
        }
    }
}