백준 17352 (C++) 여러분의 다리가 되어 드리겠습니다!

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

17352번: 여러분의 다리가 되어 드리겠습니다!

 

 

분리집합을 union해준 후, 1과 연결되지 않은 set중 아무거나 출력하면 된다.

정답이 되는 출력이 여러가지이므로 다른 방법도 가능하다.

 

 

 

코드

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
using ll = long long;
const int MAX = 300001;
int n,m;
int Parent[MAX];
int getParent(int n1) {
    if (Parent[n1] == n1) return n1;
    else return Parent[n1] = getParent(Parent[n1]);
}
void unionParent(int n1, int n2) {
    n1 = getParent(n1);
    n2 = getParent(n2);
    if (n1 != n2) {
        Parent[n2] = n1;
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i <= n; i++) {
        Parent[i] = i;
    }
    for (int i = 0; i < n-2; i++) {
        int a, b;
        cin >> a >> b;
        unionParent(a, b);
    }
    int parent_of_1 = getParent(1);
    for (int i = 2; i <= n; i++) {
        if (parent_of_1 != getParent(i)) {
            cout << "1 " << i;
            break;
        }
    }
    return 0;
}