16 - Hard - Friend Circles

반 에는 N 명의 학생 이 있다.그 중 어떤 사람 은 친구 이 고, 어떤 사람 은 그렇지 않다.그들의 우정 은 전달 성 을 가지 고 있다.A 는 B 의 친구 이 고 B 는 C 의 친구 라 는 것 을 알 고 있다 면 우 리 는 A 도 C 의 친구 라 고 생각 할 수 있다.이른바 친구 권 이란 모든 친구 의 집합 을 가리킨다.
N * N 의 행렬 M 을 지정 하여 학급 중 학생 간 의 친구 관 계 를 나타 낸다.만약 에 M [i] [j] = 1 은 i 번 째 와 j 번 째 학생 이 서로 친구 가 되 는 것 을 알 고 있 음 을 나타 낸다. 그렇지 않 으 면 모른다.너 는 모든 학생 들 이 이미 알 고 있 는 친구 권 의 총 수 를 출력 해 야 한다.
예시 1:

  : 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
  : 2 

설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 그들 은 한 친구 권 에 있다.두 번 째 학생 은 스스로 친구 권 에 있다.그래서예시 2:

  : 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
  : 1

설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 학생 1 과 학생 2 는 서로 친구 이기 때문에 학생 0 과 학생 2 도 친구 이기 때문에 그들 세 사람 은 한 친구 권 에서 1 로 돌아간다.주의:
N 은 [1, 200] 범위 내 에 있다.모든 학생 에 게 는 M [i] [i] = 1 이 있 습 니 다.M [i] [j] = 1 이 있 으 면 M [j] [i] = 1 이 있다.
자기가 쓴 것, 귀속, 비교적 느리다, 120 ms

class Solution(object):
    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        self.M = M
        self.n = len(M)
        self.circles = []
        self.done = []
        for i in range(self.n):
            self.travel(i)
        return len(self.circles)
        
    def travel(self, i):
        if i in self.done:  #   
            return
        self.done.append(i)  #     
        alone = True 
        for j in range(self.n):  #   i，           
            if i == j:
                continue
            if self.M[i][j] == 1:  #         
                alone = False
                no_circle = True
                for c in self.circles:  #              
                    if i in c:
                        no_circle = False
                        if j not in c:  #      ，       ，        
                            c.append(j)
                    elif j in c:
                        no_circle = False
                        if i not in c:
                            c.append(i)
                if no_circle:  #               ，     
                    self.circles.append([i, j])
                self.travel(j)  # ！！！！  ，                 ，           
        if alone:
            self.circles.append([i])

다른 사람 이 쓴 '44ms' 는 사실 위의 생각 과 같 지만 많이 간편 해 졌 다.

def findCircleNum(self, M):
    an = 0
    rest = list(range(len(M)))  #     
    circles = []  #    
    while rest:
        stack = [rest.pop(0)]  #        ，      
        c = []
        while stack:  #       
            cur = stack.pop()  #         
            c.append(cur)  #   
            for x in [x for x in rest if M[cur][x]]:  #    rest ， cur      
                rest.remove(x)  # 2.       rest   ，              
                stack.append(x)  # 1.        ，！！！！！！  
        circles.append(c)  #   ，        ，    
        an += 1  #    
    return an