(22967) 구름다리

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

단계별로 풀어보기

37단계(해 구성하기) 8번째

 

 

 

모든 정점 쌍이 이어진 완전 그래프일 때 지름이 1로 가장 작다. 이때 필요한 간선 수는 N(N-1)/2개인데, 우리가 쓸 수 있는 간선의 수는 최대 2N-2개이다. 따라서 N≤4일 때는 완전 그래프를 만들 수 있다.

이 경우 인접 행렬을 만들어 이어져 있지 않은 모든 두 정점을 잇는 다리를 만든다.

그 다음으로 가능한 형태는 하나의 정점에 나머지 모든 정점이 연결된 스타 그래프로 이때 지름은 2이다. 스타 그래프에 필요한 간선 수는 N-1개이므로 N에 상관없이 항상 지름이 2가 되도록 다리를 만들 수 있다.

이 경우 기준 정점을 1번으로 잡고, 1번과 연결되지 않은 다리는 전부 만들면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  
  cin >> n;
  
  if(n<=4){
    vector adj(n+1, vector<int>(n+1));
    
    for(int i=1;i<n;i++){
      int s, e;
      
      cin >> s >> e;
      
      adj[s][e]= 1;
      adj[e][s]= 1;
    }
    
    int cnt= 0;
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        if(adj[i][j]) continue;
        
        cnt++;
      }
    }
    
    cout << cnt << "\n" << 1 << "\n";
    
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        if(adj[i][j]) continue;
        
        cout << i << " " << j << "\n";
      }
    }
    
    return 0;
  }
  
  vector<int> connect(n+1);
  
  int cnt= 0;
  
  for(int i=1;i<n;i++){
    int s, e;
    
    cin >> s >> e;
    
    if(s==1){
      connect[e]= 1;
      cnt++;
    }else if(e==1){
      connect[s]= 1;
      cnt++;
    }
  }
  
  cout << n-1-cnt << "\n" << 2 << "\n";
  
  for(int i=2;i<=n;i++){
    if(connect[i]) continue;
    
    cout << 1 << " " << i << "\n";
  }
  
  return 0;
}