547. Number of Provinces

Problem

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

Solution

The idea to solve this problem is to group connected nodes.

The first thought is that we can use Union Find to group nodes.

The second way that comes to mind is that for any node, we can use DFS or BFS to find all connected nodes, and these nodes will form a group. Then, do the above-mentioned actions for any node that has not been grouped until all nodes are grouped.

Union Find

• Time: 
• Space: 

class Solution {
    class UnionFind {
        private int[] parents;
        private int count;

        UnionFind(int size) {
            count = size;
            parents = new int[size];
            for (int i = 0; i < size; i++) {
                parents[i] = i;
            }
        }

        int find(int x) {
            while (x != parents[x]) {
                x = parents[x];
                parents[x] = parents[parents[x]];
            }
            return x;
        }

        void union(int x, int y) {
            int parentX = find(x);
            int parentY = find(y);
            if (parentX == parentY) {
                return;
            } else if (parentX < parentY) {
                parents[parentY] = parentX;
            } else {
                parents[parentX] = parentY;
            }
            count--;
        }

        int getCount() {
            return count;
        }
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) continue;
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.getCount();
    }
}

DFS

• Time: 
• Space: 

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int count = 0;
        boolean[] isVisited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!isVisited[i]) {
                dfs(isConnected, i, isVisited);
                count++;
            }

        }
        return count;
    }

    private void dfs(int[][] isConnected, int i, boolean[] isVisited) {
        isVisited[i] = true;
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !isVisited[j]) {
                dfs(isConnected, j, isVisited);
            }
        }
    }
}

BFS

• Time: 
• Space: 

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int count = 0;
        boolean[] isVisited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!isVisited[i]) {
                bfs(isConnected, i, isVisited);
                count++;
            }

        }
        return count;
    }

    private void bfs(int[][] isConnected, int i, boolean[] isVisited) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(i);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            if (isVisited[v]) continue;
            isVisited[v] = true;
            for (int j = 0; j < isConnected.length; j++) {
                if (isConnected[v][j] == 1 && !isVisited[j]) {
                    queue.offer(j);
                }
            }
        }
    }
}

Reference

• 547. Number of Provinces, LeetCode.
• 547. Number of Provinces, LeetCode Solutions.