백준
백준 1325 효율적인 해킹 (파이썬)
chldkato
2020. 2. 17. 17:15
https://www.acmicpc.net/problem/1325
1325번: 효율적인 해킹
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
www.acmicpc.net
1. 양방향이 아니라 단방향으로 관계를 만들어줍니다
2. bfs로 경로를 따라 이동하면서 거리를 저장하고 최대값에 해당하는 인덱스를 오름차순으로 출력
from collections import deque
import sys
input = sys.stdin.readline
def bfs(x):
q = deque()
c = [0 for _ in range(n)]
q.append(x)
c[x] = 1
cnt = 1
while q:
x = q.popleft()
for nx in a[x]:
if c[nx] == 0:
cnt += 1
c[nx] = 1
q.append(nx)
return cnt
n, m = map(int, input().split())
a = [[] for _ in range(n)]
for _ in range(m):
x, y = map(int, input().split())
a[y-1].append(x-1)
ans = [0 for _ in range(n)]
for i in range(n):
ans[i] = bfs(i)
for i in range(n):
if ans[i] == max(ans):
print(i+1, end=' ')