Number of Provinces - Sap Labs Online Assessment Manipal University

Problem Preview

"There are `n` cities numbered from `1` to `n`. Some pairs of cities are directly connected by roads. If city `A` is connected to city `B`, and city `B` is connected to city `C`, then city `A` and city `C` are also considered to be in the same group. A **province** is a maximal group of cities that are directly or indirectly connected to each other. You are given the connectivity information of all cities in the form of an adjacency matrix. Determine the total number of provinces. ## Input Format * The first line contains a single integer `n` — the number of cities. * The next `n` lines each contain `n` integers (`0` or `1`), where the `j`-th integer in the `i`-th row indicates whether city `i` and city `j` are directly connected. ## Output Format Print a single integer — the number of provinces. ## Constraints * `1 ≤ n ≤ 200` * The matrix is symmetric. * Every city is connected to itself. ## Sample Input 1 ```text 3 1 1 0 1 1 0 0 0 1 ``` ## Sample Output 1 ```text 2 ``` ### Explanation Cities `1` and `2` belong to the same province, while city `3` forms another province. Hence, the answer is `2`. --- ## Sample Input 2 ```text 3 1 0 0 0 1 0 0 0 1 ``` ## Sample Output 2 ```text 3 ``` ### Explanation No two different cities are directly connected, so each city forms its own province. ---"