halang-log
💡 PS

[BOJ] 9372 상근이의 여행

date
Feb 6, 2022
slug
boj-9372
author
status
Public
tags
PS
summary
상근이의 여행 문제 풀이입니다.
type
Post
thumbnail
category
💡 PS
updatedAt
Aug 3, 2023 08:52 AM
언어

문제

풀이

가장 적은 종류의 비행기를 타고 모든 국가들을 여행해야 한다는 것이 포인트이다. 여기서의 종류는 간선을 의미하며 모든 국가들을 여행해야 한다는 것은 모든 정점을 포함해야 한다는 것과 같다. 이는 곧 최소 스패닝 트리를 말한다. 스패닝 트리는 그래프의 최소 연결 부분 그래프로 (N-1)개의 간선을 갖는다.

코드

#include <cstdio> using namespace std; int tc; int n, m, a, b; int main() { scanf("%d", &tc); while (tc--) { scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) scanf("%d %d", &a, &b); printf("%d\n", n-1); } }