백준 17352번 여러분의 다리가 되어 드리겠습니다![C++]

1. 문제 풀이

안녕하세요. 오늘 풀어볼 문제는 "백준 17352번 여러분의 다리가 되어 드리겠습니다!"입니다. 문제의 유형은 "disjoint-set"입니다. distjoint-set은 분리집합이라고 하며 이를 구현한 알고리즘을 union-find라고 합니다. 관련 알고리즘을 모르신다면. 유니온-파인드 알고리즘 링크를 클릭해서 내용을 공부하시고 풀어보시길 바랍니다.

 

정점이 N개이고 간선이 N-1개인 무방향 연결그래프에서 임의의 간선 하나를 삭제한 무방향 비연결 그래프가 주어졌을 때, 하나의 간선을 다시 이어 연결그래프가 되는 간선 하나를 아무거나 찾아 출력하면 됩니다. 입력으로 주어진 간선이 잇고 있는 두 정점 정보를 union 하게 되면 최종적으론 두 개의 집합이 됩니다. 그 두 집합에서 각각 아무 정점이나 찾아 출력하면 풀이할 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

vector<int> p(300'005, -1);

int find(int x){
  if(p[x] < 0) return x;
  return p[x] = find(p[x]);
}

void merge(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  if(p[x] == p[y]) --p[x];
  if(p[x] < p[y]) p[y] = x;
  else p[x] = y;
}

int n;

int main() {
  fastio(nullptr, false);

  cin >> n;
  for(int i = 0; i < n-2; i++){
    int u, v;
    cin >> u >> v;
    merge(u, v);
  }
  
  int u1 = find(1);
  for(int u2 = 2; u2 <= n; u2++){
    if(u1 == find(u2)) continue;
    cout << u1 << " " << u2;
    return 0;
  }
}

 

시간복잡도는 O(N*아커만역함수(N))입니다.

 

3. 제출결과