Number of Provinces
Medium · union find
A country has n cities, numbered 0 to n - 1. You are given a square table connected with n rows and n columns that holds only 0 and 1. If connected[i][j] is 1, there is a road directly between city i and city j; if it is 0, there is not.
Roads work in both directions, so connected[i][j] always equals connected[j][i], and every city is connected to itself, so connected[i][i] is always 1.
Two cities belong to the same province if you can travel from one to the other along roads, possibly passing through other cities on the way. No road joins two different provinces.
Return the number of provinces.
Examples
Example 1
Input: connected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
Output: 2
Cities 0 and 1 are joined by a road, and city 2 has no road to anyone else.
Example 2
Input: connected = [[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1]]
Output: 2
City 0 reaches city 2 through city 1, so cities 0, 1 and 2 form one province. City 3 is alone.
Example 3
Input: connected = [[1, 0], [0, 1]]
Output: 2
Neither city has a road to the other, so each is its own province.
Constraints
- 1 <= n <= 200, where n is the number of rows of connected
- connected has n rows and n columns, and every entry is 0 or 1
- connected[i][i] == 1 and connected[i][j] == connected[j][i] for all i and j