Number of Provinces
Given a matrix representing direct connections, find the number of connected components (provinces).
Input format
The first line contains N. The next N lines contain an N×N symmetric adjacency matrix (0 or 1, diagonal is 1).
Output format
Print the number of connected components.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
2
1 1
1 1Expected output
1Example 2
Input
12
1 0 0 1 0 0 0 0 0 0 0 0
0 1 0 1 0 1 1 1 0 1 1 0
0 0 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 0 1 0 0 0
0 0 1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 0 1 0 1 1 0
0 1 1 1 1 0 1 0 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 0
0 0 1 1 1 0 1 0 1 1 0 1
0 1 1 0 1 1 0 0 1 1 0 0
0 1 1 0 1 1 0 0 0 0 1 1
0 0 0 0 1 0 1 0 1 0 1 1Expected output
1