![https://leetcode.com/problems/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.
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
Solution:
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
58
59
60
61
62
63
64
| class Solution {
int n;
public int findCircleNum(int[][] isConnected) {
n = isConnected.length;
UF uf = new UF(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1) {
uf.union(i, j);
}
}
}
return uf.count();
}
private class UF {
private final int[] a;
private final int[] sz;
public UF(int n) {
this.a = new int[n];
this.sz = new int[n];
for (int i = 0; i < n; i++) {
this.a[i] = i;
this.sz[i] = 1;
}
}
int find(int p) {
while (a[p] != p) {
p = a[p];
}
return p;
}
void union(int p, int q) {
int pid = find(p);
int piq = find(q);
if (sz[pid] >= sz[piq]) {
a[piq] = pid;
sz[pid]+=sz[piq];
} else {
a[pid] = piq;
sz[piq] += pid;
}
}
int count() {
int counter = 0;
for (int i = 0; i < n; i++) {
if (a[i] == i) {
counter++;
}
}
return counter;
}
}
}
|