Count the provinces

Not practiced yet: connected components, graph DFS, visited set, adjacency list, set.add +1. Try it anyway, or do those reps first.

There are n cities. is_connected is an n x n matrix where is_connected[i][j] == 1 means cities i and j have a direct road (the matrix is symmetric and is_connected[i][i] == 1). Cities linked directly or through other cities form one province. Return the number of provinces.

Examples

inis_connected = [[1,1,0],[1,1,0],[0,0,1]]out2

inis_connected = [[1,0,0],[0,1,0],[0,0,1]]out3

inis_connected = [[1]]out1

main.pypracticePython