[백준 2606] 바이러스

 

www.acmicpc.net/problem/2606

2606번: 바이러스

간단한 bfs 문제이다. 답을 출력할때 1번에 의해 감염된 컴퓨터수 이니 카운팅할때 1번 컴퓨터는 제외해주자.

import sys
from collections import deque
N = int(input())
M = int(input())

near = [[] for _ in range(N+1)]


for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    near[u].append(v)
    near[v].append(u)

ans = -1

q = deque()

q.append(1)
visit = set()
while q :
    now = q.popleft()
    if now in visit:
        continue
    visit.add(now)
    ans += 1
    for i in near[now]:
        if i not in visit:
            q.append(i)

print(ans)