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

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

 

전형적인 분리집합 문제이다.

주어진 edge의 vertex를 모두 union하게 되면 입력 조건에 의해 단 한개의 구간만 parent가 다르게 나온다.

이를 나머지 vertex 중 아무 것과 잇게되면 어떤 두 섬 사이든 왕복할 수 있게 된다.

 

#include <iostream>
#include <vector>


using namespace std;


int parent[300001];

int findParent(int k){
    if (parent[k] == k) {
        return k;
    }
    return parent[k] = findParent(parent[k]);
}

void merge(int a, int b){

    if (findParent(a) == findParent(b)) {
        return;
    } else if (a < b) {
        parent[findParent(b)] = findParent(a);
    } else if (b < a) {
        parent[findParent(a)] = findParent(b);
    }


}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;

    cin >> n;

    vector<int> g[n + 1];

    for (int i = 0; i < n - 2; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);

    }

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            merge(i, g[i][j]);
        }
    }

    int temp = findParent(1);
    for (int i = 2; i <= n; i++) {
        if (temp != findParent(i)) {
            cout << temp << " " << findParent(i);
            return 0;
        }
    }


    return 0;
}