(9372) 상근이의 여행

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

단계별로 풀어보기

35단계(최소 신장 트리) 1번째

 

 

 

최소 신장 트리의 개념과 특징에 대해 이해하는 문제

이미 입력이 연결 그래프라는 보장이 조건으로 주어졌고, 연결 그래프가 되기 위한 간선의 최소 개수는 정점 개수에서 1을 뺀 값이므로 입력받은 정점 개수-1을 출력하면 된다. 다른 값은 전부 필요 없다.

 

 

 

#include <iostream>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n, m;
    
    cin >> n >> m;
    
    while(m--){
      int a, b;
      
      cin >> a >> b;
    }
    
    cout << n-1 << "\n";
  }
  
  return 0;
}