[BOJ] 17532 여러분의 다리가 되어 드리겠습니다! - C++

 

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

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

아이디어

n개의 섬이 n-1개의 다리로 모두 이어져 있다가 하나가 끊어졌으므로 2개의 그룹으로 섬을 분류할 수 있다. 각 그룹에서 섬을 하나씩 뽑아 서로 이으면 모든 섬을 다닐 수 있다.

여러 섬이 서로 이어져있는지 확인하기 위해 Union-Find를 사용한다.

 

단계

1. 이어진 다리에 대해 Union-Find 수행
2. 서로 다른 그룹인 두 섬을 출력하면 되는데 아무 경우나 가능하므로 한 섬을 1번 섬으로 고정한다. 따라서, 1번 섬과 다른 그룹인 섬의 번호를 출력한다.

 

코드

#include <iostream>

using namespace std;

int n;
int parents[300'001];

int find(int k) {
    if (parents[k] == k)
        return k;
    else
        return parents[k] = find(parents[k]);
}

void uni(int a, int b) {
    int pa = find(a);
    int pb = find(b);

    if (pa < pb)
        parents[pb] = pa;
    else
        parents[pa] = pb;
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++)
        parents[i] = i;

    for (int i = 0; i < n - 2; i++) {
        int a, b;
        cin >> a >> b;
        uni(a, b);
    }

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