Number Of Provinces Problem
Description
LeetCode Problem 547.
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 i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
Example 1:
1
2
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Example 2:
1
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]
Sample C++ Code using Union Find
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
class Solution {
public:
int _find(int p, vector<int>& num) {
while (p != num[p])
p = num[p];
return p;
}
void _union(int i, int j, vector<int>& num) {
int r1 = _find(i, num);
int r2 = _find(j, num);
num[r1] = r2;
}
int findCircleNum(vector<vector<int>>& M) {
int n = M.size();
vector<int> parent(n);
for (int i = 0; i < n; i ++)
parent[i] = i;
int r1, r2;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (i == j) continue;
if (M[i][j] == 0) continue;
_union(i, j, parent);
}
}
unordered_map<int, int> mp;
for (int i = 0; i < n; i ++)
mp[_find(i, parent)] = 1;
return mp.size();
}
};