문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
bfs를 이용해서 푸는 문제였다.
5 4
3 1
3 2
4 3
5 3
입력값이 위와 같이 a,b로 들어올 때 b노드에 a노드가 연결되어있다는 식으로 값을 저장하면 된다.
-> graph[b].append(a)
visited 방문 표시배열은 초기화해줘야 한다!
bfs 함수안에 넣어서 초기화 해주면 된다.
백준에서는 pypy3으만 돌아간당..
input 말고 sys.stdin.readline()쓸것..!
from collections import deque
import sys
n,m=map(int,sys.stdin.readline().split())
graph=[[] for i in range(n+1)]
for i in range(m):
a,b=map(int,sys.stdin.readline().split())
graph[b].append(a)
def bfs(graph,start):
queue=deque([start])
visited=[False]*(n+1)
visited[start]=True
count=1
while queue:
v=queue.popleft()
for i in graph[v]:
if visited[i]==False:
visited[i]=True
queue.append(i)
count+=1
return count
answer=[]
for i in range(1,n+1):
answer.append(bfs(graph,i))
max_v=max(answer)
for i in range(len(answer)):
if answer[i]==max_v:
print(i+1,end=' ')