GraphUnion FindDFS
There are n cities. Some are directly connected, and connectivity is transitive: if city a is connected to b and b to c, then a and c are in the same province. You are given an n x n matrix where 1 means two cities are directly connected. Count the provinces (groups of connected cities).
Input
Line 1: n. Next n lines: n values each (0 or 1). The matrix is symmetric and the diagonal is 1.
Output
Print the number of provinces.
Constraints
1 <= n <= 200
Example 1
Input
3 1 1 0 1 1 0 0 0 1
Output
2
Cities 0 and 1 form one province and city 2 forms another.