[백준] 2606번: 바이러스

가영·2021년 2월 23일
0

알고리즘

목록 보기
25/41
post-thumbnail

문제보기

1번 정점이랑 이어진 애들 전부 구하면 됨: BFS로 품


무방향 무방향 무방향
엣지 입력받을 때 둘 다 해줘 제발

from _collections import deque
N = int(input())
M = int(input())
graph = [[0]*N for _ in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    graph[i-1][j-1] = 1
    graph[j-1][i-1] = 1 # 또 까먹으면 너는 진짜...

visited = [False]*N
queue = deque([0])
cnt = 0
while queue:
    s = queue.popleft()
    if not visited[s]:
        visited[s] = True
        cnt += 1
        for e in range(N):
            if graph[s][e]:
                queue.append(e)
print(cnt-1) # 1번은 빼고 세줘야 하니까

0개의 댓글