Number of Provinces

Problem

Count the connected components (provinces) in an undirected graph given as an adjacency matrix.

is_connected is an n by n matrix where a 1 at row i column j means nodes i and j are directly connected. Union the endpoints of every edge and count the distinct roots. An empty graph has 0 provinces.

Return the number of provinces.

Hint

Union i and j for every 1 above the diagonal, then count distinct roots.

Test cases

case 1

in: [[[1,1,0],[1,1,0],[0,0,1]]]

expected: 2

case 2

in: [[[1,0],[0,1]]]

expected: 2

case 3

in: [[[1,1,1],[1,1,1],[1,1,1]]]

expected: 1

case 4

in: [[]]

expected: 0

case 5

in: [[[1]]]

expected: 1

Starter codePython

def count_provinces(is_connected):
    # Your code here
    pass

5 test cases · run your code against them in the editor