Problem statement

https://leetcode.com/problems/number-of-provinces/

Solution

We need to find number of connected components in graph on $n$ nodes. Be careful, it is similar to problem 0200 Number of Islands, but here we have n nodes, not n^2 and what is given here is adjacency matrix. So, just perform any dfs or bfs traversal with (n^2) time complexity and O(n) space. We can not really do better than O(n^2) here, because we need to look at our matrix at least one time.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def findCircleNum(self, M):
        n, comp = len(M), 0
        visited = [0]*n
        
        def dfs(x):
            if visited[x]: return
            visited[x] = 1
            for i in range(n):
                if M[x][i] == 1: dfs(i)
        
        for i in range(n):
            if visited[i] == 0:
                dfs(i)
                comp += 1
        
        return comp

Remark

There is also Union Find solution with the same complexity.