-
Notifications
You must be signed in to change notification settings - Fork 22
/
547.number-of-provinces.cpp
57 lines (55 loc) · 1.69 KB
/
547.number-of-provinces.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Tag: Depth-First Search, Breadth-First Search, Union Find, Graph
// Time: O(N^2)
// Space: O(N)
// Ref: -
// Note: -
// 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]
//
//
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size(), count = 0;
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(isConnected, i, visited);
++count;
}
}
return count;
}
void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited) {
visited[i] = true;
for (int k = 0; k < isConnected.size(); ++k) {
if (isConnected[i][k] == 1 && !visited[k]) {
dfs(isConnected, k, visited);
}
}
}
};