LeetCode Daily Question 17

4 月 6 日 每日一题

题目：547. Number of Provinces

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.

1
2
3
4
5

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

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

思路

遍历所有 vertex，如果当前 vertex 为 unvisited，num++，并且使用 dfs 遍历该所有和该节点在一个 province 的节点，并把他们标记为 visited。dfs 结束后回到原函数继续对剩余 vertex 进行遍历。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    void dfsHelper(vector<vector<int>>& isConnected, vector<bool>& visited, int i){
        visited[i] =true;
        for(int j = 0; j < isConnected.size(); j++){
            if(isConnected[i][j] && !visited[j]){
                dfsHelper(isConnected, visited, j);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<bool> visited(isConnected.size(),false);
        int circleNum = 0;
        for(int i = 0; i < visited.size(); i++){
            if(!visited[i]){
                circleNum++;
                dfsHelper(isConnected, visited, i);
            }
        }
        return circleNum;
    }
};