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

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

---

문제 )

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

"왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데...

 

 

입력 :

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

 

 

 

출력 :

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <set>
 
using namespace std;
 
// 재귀함수를 이용, 부모를 찾음
int get_parent(vector<int> &parent, int x)
{
    // 자기 자신이 나온다면 끝.
    if (parent[x] == x) return x;
    // 해당 parent[x]의 부모 노드를 찾으러 간다. (재귀)
    return parent[x] = get_parent(parent, parent[x]);
}
 
 
void union_parent(vector<int> &parent, int a, int b)
{
    // 두 노드가 연결되어 있는 경우, 
    // 노드 번호가 작은 노드가 부모가 된다.
    a = get_parent(parent, a);
    b = get_parent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
int main()
{
    vector<int> parent{-1};
    
    int n;
    cin >> n;
    // union-find를 하기 위해,
    // 각 노드는 자기 자신을 부모 노드로 갖는다.
    for (int i = 1; i <= n; i++)
    {
        parent.push_back(i);
    }
 
    // 무너지지 않은 다리 연결
    for (int i = 0; i < n - 2; i++)
    {
        int a, b;
        cin >> a >> b;
        // 두 다리를 연결하면서, 부모노드를 지정해준다.
        union_parent(parent, a, b);
    }
 
    // 부모를 찾아 temp에 담는다.
    set<int> temp;
    for(int i = 1; i < parent.size(); i++)
    {
        temp.insert(get_parent(parent, i));
    }
 
    for (auto& ele : temp)
    {
        cout << ele << " ";
    }
 
    return 0;
}

 

---

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

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