백준 알고리즘 17352번 : 여러분의 다리가 되어 드리겠습니다!

링크

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

sol1) 유니온 파인드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

struct UnionFind {
	vector<int> parent, cnt;
	UnionFind(int n) : parent(n), cnt(n, 1) {
		iota(parent.begin(), parent.end(), 0);
	}
	int Find(int x) {
		return x == parent[x] ? x : parent[x] = Find(parent[x]);
	}
	bool Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return 0;
		if (a > b) swap(a, b);
		parent[b] = a;
		cnt[a] += cnt[b];
		return 1;
	}
};

int32_t main(){
  fastio;
  int N; cin >> N;
  UnionFind UF(N + 1);
  for(int i = 0; i < N - 2; i++){
    int a,b; cin >> a >> b;
    UF.Union(a, b);
  }
  for(int i = 1; i <= N; i++){
    if(i == UF.Find(i)) cout << i << ' ';
  }
}

Disjoint Set 을 이용하면 된다.
각각의 섬들을 집합으로 표현을 할 수 있고, 다리를 이을 두 섬의 번호를 출력하라고 하였으니 그냥 1~n까지 돌면서 i가 루트번호와 동일할 때는 그 정점이 곧 루트이기 때문에 이어주면 된다.
즉, 루트 노드들만 찾아주면 되는 것!