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 Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

There are n cities. Some are connected directly, and some are connected indirectly through a chain of cities. A province is a group of directly or indirectly connected cities. Given an n×n matrix isConnected where isConnected[i][j] = 1 means cities i and j are directly connected, return the total number of provinces.

Examples

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

Constraints

1 ≤ n ≤ 200 n == isConnected.length == 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.