백준 1325 효율적인 해킹 파이썬

해결방법

노드를 타고 올라가면서 카운트를 +1 해준다. 이 카운트의 값이 최댓값이라면 배열을 하나 만들어 추가해준다. 최종적으로 배열에는 (카운트의 값이 최대값인) -> (가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호) 컴퓨터들의 번호가 저장되어 있다.

from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]

def bfs(start):
    q = deque()
    q.append(start)
    visited = [False  for _ in range(n+1)]
    visited[start] = True
    cnt = 1
    while q:
        x = q.popleft()
        for v in graph[x]:
            if not visited[v]:
                visited[v] = True
                cnt += 1
                q.append(v)
    return cnt

for _ in range(m):
    a,b = map(int,input().split())
    graph[b].append(a) # a가 b를 신뢰한다고 적혀있었으므로
    #b에는 노예(?)들인 a를 저장해둔다.

max_cnt = 1
result = []
for i in range(1,n+1):
    cnt = bfs(i)
    if cnt > max_cnt:
        max_cnt = cnt
        result.clear()
        result.append(i)
    elif cnt == max_cnt:
        result.append(i)

print(*result) #괄호벗기기