백준 9372 - 상근이의 여행 [Python]

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

9372번: 상근이의 여행

 

간선의 개수를 최소로 해서 모든 정점을 잇는 그래프는 트리이고, 이때 간선의 개수는 N - 1 개이다. 간선의 정보는 사용할 필요가 없다.

 

 

템플릿 코드

import sys, math
import heapq
 
from collections import deque
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
#input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
#gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
#prime
def isPrime(x):
    if x<=1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True
 
# Union Find
# p = {i:i for i in range(1, n+1)}
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
def getPow(a, x):
    ret = 1
    while x:
        if x&1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x>>=1
    return ret
 
def getInv(x):
    return getPow(x, MOD-2)

 

for tc in range(ip()):
    n, m = mip()
    for i in range(m):
        d = lmip()
    print(n - 1)