547. Number of Provinces

[songyy5517]

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

Intuition This problem can be basically converted into the travarsal of graph using DFS. A strightforward idea is to check each node in the graph. If the current node is visited, then just skip; otherwise, there is a new province and update the number of provinces, then travarse the graph starting from the this node and set the all the encountered node to visited.

[songyy5517]

Approach: DFS

1. Exception handling;
2. Define variables:
   • isVisited: records each node whether it is visited;
   • num : the number of provinces.
3. Check each node in the graph: （1）If it is visited, then just skip to the next node; （2）Otherwise, update num ,travarse the graph starting from the current node using DFS, and set all encountered nodes to visited.
4. Return num.

Complexity Analysis

• Time complexity: $O(N^2)$ , we need to check each node and its possible edge, that is, each element in isConnected, which takes $O(N^2)$ time.
• Space complexity: $O(N)$ , additionally define a $O(N)$ visit array, and the depth of DFS is $N$ in the worst case.

[songyy5517]

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // Intuition: Travarsal of Graph, DFS
        // 1. Exception Handling
        if (isConnected == null || isConnected.length == 0 || isConnected[0].length == 0)
            return 0;

        // 2. Define variables
        boolean[] isVisited = new boolean[isConnected.length];
        int num = 0;

        // 3. Travarsing the graph
        for (int i = 0; i < isConnected.length; i++){
            if (!isVisited[i]){
                num ++;
                DFS(isConnected, isVisited, i);
            }
        }

        return num;
    }

    void DFS(int[][] isConnected, boolean[] isVisited, int idx){
        // 递归出口
        if (isVisited[idx])
            return ;

        isVisited[idx] = true;

        for (int j = 0; j < isConnected.length; j++){
            if (isConnected[idx][j] == 1)
                DFS(isConnected, isVisited, j);
        }
    }
}

[songyy5517]

2024/6/18