9372_상근이의 여행

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

 

 

트리 구조를 하나 만들고 그래프를 순회하면서 트리를 도록 순서를 짰다

 

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    graph = [ [] for __ in range(n+1) ]
    for __ in range(m):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)

    tree = [0] * (n+1)
    cnt=0
    tree[1]=1
    for i in range(1,n+1):
        for j in graph[i]:
            if not tree[j]:
                tree[j] =1
                cnt +=1
    print(cnt)

 

그런데 가만 생각해보니 해당 문제는 결국 비행기의 종류를 찾는건데, 노드가 n개라면 n개의 노드를 만드는 트리구조의 간선은 무조건 n-1개라는생각이 들어서 그냥 n-1을 출력하게 해 보았다.

 

 

 

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n,m = map(int,input().split())
    for __ in range(m):
        input()
    print(n-1)

이렇게 해도 잘 통과된다 ㅋㅋ..