Problem statement

https://binarysearch.com/problems/Friend-Groups/

Solution

Variation of Leetcode 0547. Number of Provinces, about connected components.

Complexity

It is O(n + m) for time and O(n) for space.

Code

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