547. Friend Circles

Number of Provinces - LeetCodeLeetCode

画成关系图就可以看出来，是连通图的遍历问题，BFS 和 DFS 都可以解，先用 BFS 写

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        circle = 0
        visited = set()
        for i in range(len(M)):
            if i not in visited:
                visited.add(i)
                # 直接++cirle，因为学生至少在一个朋友圈里（自己）
                circle += 1
                queue = collections.deque([i])
                while queue:
                    friend = queue.popleft()
                    # 其实就是在遍历i学生的朋友关系
                    for n, j in enumerate(M[friend]):
                        if n not in visited and j == 1:
                            # 是他朋友的就加进visited，不用再去计circle了
                            visited.add(n)
                            # 加进queue，去访问 indirect friends
                            queue.append(n)
        return circle