Leetcode（547）—— Number of provinces

subject

Yes $n$ Cities , Some of them are connected to each other , Others are not connected . If the city $a$ And the city $b$ Direct connection , And the city $b$ And the city $c$ Direct connection , So the city $a$ And the city $c$ Indirectly connected .

Province It's a group of directly or indirectly connected cities , There are no other cities in the group that are not connected .

To give you one $n\times n$ Matrix $isConnected$, among $isConnected[i][j]=1$ It means the first one $i$ Two cities and $j$ The two cities are directly connected , and $isConnected[i][j]=0$ The two are not directly connected .

Back in the matrix Province The number of .

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

Tips ：

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

Answer key

Method 1 ：DFS

Ideas

​​   The idea of depth first search is very intuitive . Traverse all cities , For every city , If the city has not been visited , Then start the depth first search from the city , Through the matrix $\text{isConnected}$ Get what cities are directly connected to the city , These cities and the city belong to the same connected component , Then continue the depth first search for these cities , Until all cities of the same connected component are visited , You can get a province . After traversing all the cities , You can get the total number of connected components , That is, the total number of provinces .

Code implementation

Leetcode Official explanation （ recursive ）：

class Solution {
    
public:
    void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int cities, int i) {
    
        for (int j = 0; j < cities; j++) {
    
            if (isConnected[i][j] == 1 && !visited[j]) {
    
                visited[j] = 1;
                dfs(isConnected, visited, cities, j);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
    
        int cities = isConnected.size();
        vector<int> visited(cities);
        int provinces = 0;
        for (int i = 0; i < cities; i++) {
    
            if (!visited[i]) {
    
                dfs(isConnected, visited, cities, i);
                provinces++;
            }
        }
        return provinces;
    }
};

My own （ iteration ）：

class Solution {
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
    
        //  The adjacency matrix of an undirected graph is known , Find the number of connected components in the graph 
        int size = isConnected.size(), ans = 0, city;
        stack<int> tmp;
        vector<bool> visited(size, false);
        for(int n = 0; n < size; n++){
    
            //  The city has not been divided into provinces 
            if(visited[n] == false){
    
                ++ans;
                tmp.push(n);
                while(!tmp.empty()){
    
                    city = tmp.top();
                    tmp.pop();
                    if(visited[city] == true) continue;
                    visited[city] = true;   //  Division of provinces 
                    for(int i = 0; i < size; i++)
                        if(isConnected[city][i] == 1) tmp.push(i);
                }
            }
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n^2)$, among $n$ It's the number of cities . Need to traverse the matrix $\text{isConnected}$ Every element in .
Spatial complexity ：$O(n)$, among $n$ It's the number of cities . You need to use an array $\text{visited}$ Record whether each city has been visited , The length of the array is $n$, The depth of the recursive call stack will not exceed $n$.

Method 2 ：BFS

Ideas

​​   You can also get the total number of provinces by breadth first search . For every city , If the city has not been visited , Then start breadth first search from the city , Until all cities in the same connected component are visited , You can get a province .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
    
        int cities = isConnected.size();
        vector<int> visited(cities);
        int provinces = 0;
        queue<int> Q;
        for (int i = 0; i < cities; i++) {
    
            if (!visited[i]) {
    
                Q.push(i);
                while (!Q.empty()) {
    
                    int j = Q.front(); Q.pop();
                    visited[j] = 1;
                    for (int k = 0; k < cities; k++) {
    
                        if (isConnected[j][k] == 1 && !visited[k]) {
    
                            Q.push(k);
                        }
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }
};

My own （ Iterative writing ）：

class Solution {
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
    
        //  The adjacency matrix of an undirected graph is known , Find the number of connected components in the graph 
        int size = isConnected.size(), ans = 0, city;
        queue<int> tmp;
        vector<bool> visited(size, false);
        for(int n = 0; n < size; n++){
    
            //  The city has not been divided into provinces 
            if(visited[n] == false){
    
                ++ans;
                tmp.push(n);
                while(!tmp.empty()){
    
                    city = tmp.front();
                    tmp.pop();
                    if(visited[city] == true) continue;
                    visited[city] = true;   //  Division of provinces 
                    for(int i = 0; i < size; i++)
                        if(isConnected[city][i] == 1) tmp.push(i);
                }
            }
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n^2)$, among $n$ It's the number of cities . Need to traverse the matrix $\text{isConnected}$ Every element in .
Spatial complexity ：$O(n)$, among $n$ It's the number of cities . You need to use an array $\text{visited}$ Record whether each city has been visited , The length of the array is $n$, The number of elements in the queue used by breadth first search will not exceed $n$.

Method 3 ： Union checking set

Ideas

​​   Another way to calculate the number of connected components is to use union search set . At the beginning , Each city belongs to a different connectivity component . ergodic matrix $\text{isConnected}$, If there is a connection between two cities , Then they belong to the same connected component , Merge them .

​​   ergodic matrix $\text{isConnected}$ After all the elements of , Calculate the total number of connected components , That is the total number of provinces .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int Find(vector<int>& parent, int index) {
    
        if (parent[index] != index) {
    
            parent[index] = Find(parent, parent[index]);
        }
        return parent[index];
    }

    void Union(vector<int>& parent, int index1, int index2) {
    
        parent[Find(parent, index1)] = Find(parent, index2);
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
    
        int cities = isConnected.size();
        vector<int> parent(cities);
        for (int i = 0; i < cities; i++) {
    
            parent[i] = i;
        }
        for (int i = 0; i < cities; i++) {
    
            for (int j = i + 1; j < cities; j++) {
    
                if (isConnected[i][j] == 1) {
    
                    Union(parent, i, j);
                }
            }
        }
        int provinces = 0;
        for (int i = 0; i < cities; i++) {
    
            if (parent[i] == i) {
    
                provinces++;
            }
        }
        return provinces;
    }
};

My own ：

class Solution {
    
    int Find(vector<int>& citys, int city){
    
        if(citys[city] == city) return city;
        else return citys[city] = Find(citys, citys[city]);
    }
    void Union(vector<int>& citys, int city1, int city2){
    
        citys[Find(citys, city2)] = Find(citys, city1);	//  Connect the two sets 
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
    
        //  The adjacency matrix of an undirected graph is known , Find the number of connected components in the graph 
        int size = isConnected.size(), ans = 0, city, root1, root2;
        vector<int> citys;
        //  Create and query an array 
        for(int n = 0; n < size; n++) 
            citys.push_back(n);
        for(int n = 0; n < size; n++){
    
            for(int i = 0; i < size; i++){
    
                if(isConnected[n][i] == 1)
                    Union(citys, n, i);
            }
        }
        for(int n = 0; n < size; n++)
            if(citys[n] == n) ans++;
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n^2\log n)$, among $n$ It's the number of cities . Need to traverse the matrix $\text{isConnected}$ All elements in , The time complexity is $O(n^2)$, If you encounter a connection , You need to do $2$ Find and maximum $1$ The merger , A total of $2n^2$ Find and maximum $n^2$ The merger , So the total time complexity is $O(2n^2\log n^2)=O(n^2\log n)$. The join set here uses path compression , However, rank merging is not used , The worst-case time complexity is $O(n^2\log n)$, The average time complexity is still $O(n^2\alpha (n))$, among $\alpha$ Is the inverse of the Ackerman function ,$\alpha (n)$ It can be considered a very small constant .
Spatial complexity ：$O(n)$, among $n$ It's the number of cities . You need to use an array $\text{parent}$ Record the ancestors of the connected components to which each city belongs .