Number of Provinces Problem

Number of Provinces Problem — ExecCode Easy DSA Practice

Solve the Number of Provinces problem on ExecCode. Free online easy DSA practice in Matrix. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise. Your task is to compute the required answer and return the total number of provinces . There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group.

Examples

Input isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 0, 1, 1]]; Output 1. Input isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]; Output 3. Input isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]; Output 2

Constraints

1 <= n <= 200 n == isConnected.length n == isConnected[i].length isConnected[i][j] is 1 or 0. isConnected[i][i] == 1 isConnected[i][j] == isConnected[j][i]

Practice Number of Provinces free on ExecCode. Browse DSA problems, topic map, and placement guides.