Boj 17352 c++ 여러분의 다리가 되어드리겠습니다!

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

 

N개의 마을을 연결하는 N-1개의 다리가 있었다. 

하지만 다리가 하나 무너지며 모두 연결되어 있던 마을 중에서 서로 이동이 불가능한 마을이 생기게 되었다.

이때, 두 마을을 다시 잇는 다리를 지어 모든 마을을 다시 연결되게 하려고 한다.

 

무너지지 않은 N-2개의 다리들에 대한 정보가 주어질 때, 이어야 하는 두 마을을 구하는 문제이다.

 

 

풀이 : N-2개의 간선에 대한 정보를 바탕으로 union 해주고, 루트노드를 1로 설정한 뒤, 서로 다른 집합에 속한 노드의 대표 원소를 

구한다.

 

이 둘을 이으면 다시 모든 마을이 연결된다.

 

#include <iostream>
#define Max 300001
using namespace std;

int parent[Max];

int Find(int x) {
    if(parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

void Solve() {

    int N, ans, root;
    cin >> N;
    for(int i = 0; i < N-2; i++) {
        int a, b;
        cin >> a >> b;
        Union(a, b);
    }
    root = Find(1);

    for(int i = 2; i <= N; i++){
        if(root != Find(i)){
            ans = Find(i);
            break;
        }
    }
    cout << root << " " << ans;
}

int main() {

    for(int i = 0; i < Max; i++){
        parent[i] = i;
    }

    Solve();
}