문제

https://www.acmicpc.net/problem/1325

나의 코드

"""
1. 아이디어
A가 B를 신뢰할 때 B를 해킹하면 A가 감염되는 단방향 관계가 성립되므로 
무방향 그래프가 아닌 방향그래프로 작성 해야 한다!

오름차순으로 출력하기 위해 해킹된 컴퓨터 개수를 저장하는 변수를 따로 저장하고 
오름차순으로 정렬해야 한다!


2. 시간복잡도
O(V(V+E)) 인가?
V 는 10,000 E는 100,000이고 이걸 노드의 개수만큼 반복하니깐 저 시간복잡도가 나오는거 같다.
그럼 10^9 = 1억, 파이썬은 1초에 2천만번 연산하니깐 5초고 문제 제한시간은 5초;;
아슬아슬한데 근데 뭐 단방향 그래프니깐 저거보단 시간이 덜 걸리지 않을까 싶다.
안되면 pypy로 제출해야지
"""

from collections import deque
from sys import stdin
input = stdin.readline

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

for _ in range(m):
    a, b = map(int, input().split())
    graph[b].append(a)

def bfs(x):
    """ 이게 처음에는 방문 여부를 왜 체크해줘야 싶었는데 생각해보면 예제의 경우 말고 다른경우
    즉, 3에서 2로가고 다시 2에서 3으로 갈때 가면 안되는데 방문여부 체크 안해줘서 
    또 +1될 수 있어서 방문 여부 체크 해줘야 하는거 같다. """
    visited = [False] * (n+1)
    visited[x] = True
    q = deque([x])
    cnt = 0

    while q:
        node = q.popleft()

        for i in graph[node]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                cnt += 1

    return cnt

max_cnt = 0

for i in range(1, n+1):
    cnt = bfs(i)

    max_cnt = max(max_cnt, cnt)
    answer.append((i, cnt))

for idx, value in answer:
    if value == max_cnt:
        print(idx, end=" ")
    

느낀점

python3는 안되고 pypy로 하면 12초가 뜨면서 맞았다고 떴다. 근데 12초가 뜨는데 왜 통과가 된건지는 잘 모르겠다;;