[백준, 9372번] 상근이의 여행

풀이

• start를 이용해서 연결되어 있는 국가가 하나인 경우를 찾고자 했음
  • 굳이 안해도 되는 것 같음
• 아래 코드는 일반적인 방문 체크를 통해 풀이하는 코드
• 특징으로는 bfs를 통해 풀었기에 q에 추가할 때 방문 체크를 하여
  • 같은 나라가 q에 똑같이 들어있지 않도록 하기!

 

import sys

input = sys.stdin.readline

from collections import deque

for _ in range(int(input())):

    n,m = map(int,input().split())

    _dic = {i:[] for i in range(1,n+1)}

    result = 0

    for _ in range(m):

        a,b = map(int,input().split())

        _dic[a].append(b)

        _dic[b].append(a)

    start = min(_dic, key=lambda x: len(_dic[x]))

    visit = [0]*(n+1) # 방문 국가 체크

    q = deque([start])

    visit[start] = 1

    while q:

        s = q.popleft() # bfs 사용

        for i in _dic[s]:

            if not visit[i]:

                visit[i] = 1

                result += 1

                q.append(i)

    print(result)