책너두 - 알고리즘 챌린지[11/20]

오늘의 문제 : 상근이의 여행

DFS를 이용해서 풀었는데,

다른 분들 풀이의 공통적으로 전체가 연결되어 있기 때문에 DFS를 순회할 필요없이, N-1이 정답이라고..ㅋㅋ..

import sys
from collections import defaultdict

def dfs(start, cnt) :
    visited[start] = 1
    for end in flight[start] :
        if visited[end] == 0 :
            cnt = dfs(end, cnt+1)
    return cnt

t = int(sys.stdin.readline().strip())


for _ in range(t) :
    flight = defaultdict(set)
    n, m = map(int, sys.stdin.readline().split())
    visited = [0] * (n+1)
    for _ in range(m) :
        nat1, nat2 = map(int, sys.stdin.readline().split())
        flight[nat1].add(nat2)
        flight[nat2].add(nat1)

    res = dfs(1, 0)

    print(res)