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

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

1. 문제

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

어제까지는 그랬다.

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

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

2. 입력

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

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

3. 출력

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

4. 풀이

• 분리 집합 문제
• 서로 부모가 다른 두 노드를 찾아 둘을 출력하면 된다.
• N을 입력 받고 1부터 N까지 부모를 자기 자신으로 초기화 해준다.
• N-1개의 다리 정보를 입력 받는다.
  • 두 다리를 합집합해준다.
• 부모가 다른 두 노드를 아무거나 찾아서 출력한다.

5. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int parent[300001];

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

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

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


int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> n;

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

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

    unionParent(a, b);
  }

  int a = -1;
  int b = -1;

  for (int i = 1; i <= n; i++) {
    if (a == -1) {
      a = findParent(i);
    }
    else {
      if (a != findParent(i)) {
        b = findParent(i);
        break;
      }
    }
  }
  cout << a << " " << b;
}