547.md

547 Friend Circles

Description

link

---

Solution

• 并查集解法 union find，把所有见到过的全部放到记录set当中，保证主循环中没有见到过的都是新的集合

---

Code

最坏情况：O(n^2)

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        if not M:
            return 0
        
        visited = set()
        N = len(M)
        res = 0
        for i in range(N):
            if i not in visited:
                res += 1
                self.dfs(M, i, visited)
        return res
    
    
    def dfs(self, M, i, visited):
        visited.add(i)
        for idx, adj in enumerate(M[i]):
            if adj == 1 and idx not in visited:
                self.dfs(M, idx, visited)
        return