import sys
from collections import deque
N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
graph = [[False] * (N + 1) for _ in range(N + 1)]
for i in range(1, M + 1):
node1, node2 = list(map(int, sys.stdin.readline().rstrip().split()))
graph[node1][node2] = True
graph[node2][node1] = True
q = deque([1])
visited = [0] * (N + 1)
while q:
prev = q.popleft()
for i in range(1, N+1):
if graph[prev][i] and visited[i] == 0:
q.append(i)
if i != 1:
visited[i] = 1
print(sum(visited))
bfs로 풀었다
그런데 마지막에 visited
부분을 더한 후 -1 하는 방식으로 했을 때는 에러가 발생했는데, visited
배열자체를 채울 때 1번이면 무시하는 방식으로 갔더니 정답이 되었다.
뭔가 예외인 경우가 있...는 것 같다.
교훈) 리터럴하게 값을 더하거나 빼면 위험하다. 코드가 조금 길어져도 계산 과정에서 거르는게 정답이다.