Number of Provinces
mediumGraphs+20 XPTime limit 2s
There are n cities. connected[i][j] = 1 means cities i and j are directly connected (the matrix is symmetric and connected[i][i] = 1). A province is a group of cities connected directly or indirectly, with no connection outside the group. Count the provinces.
Input:
- line 1:
n - next
nlines:nvalues (0 or 1) each
Output: the number of provinces.
Constraints: 1 ≤ n ≤ 200.
Think about it: this is counting connected components: start a DFS/BFS from every unvisited city, or use Union-Find (disjoint set union) and count the roots.
Sample input 1
3 1 1 0 1 1 0 0 0 1
Sample output 1
2
Sample input 2
3 1 0 0 0 1 0 0 0 1
Sample output 2
3
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).