문제
https://www.acmicpc.net/problem/17352
문제해설
섬의 개수 N이 주어지고 N-2개의 두 섬을 잇는 다리가 주어진다.
a b의 형태로 주어지고
a와 b를 잇는 다리인 것이다.
우리가 구해야 하는 것은 모든 섬을 잇기 위해
추가로 놓아야 하는 다리이다.
여러개가 정답일 수 있고 아무거나 출력하면 된다.
문제풀이
단순한 유니온파인드 문제이다.
입력으로 주어지는 다리들을 전부 유니온하고
전체 노드들을 반복문으로 돌며
1과 연결되지 않은 노드를 찾아서 1과 연결시키면 된다.
여기서 1과 비교하는 이유는 스페셜 저지여서
아무거나 출력해도 되기 때문이다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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 merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
parent[y] = x;
}
bool isUnion(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return true;
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
for (int i = 0; i < MAX; i++)
parent[i] = i;
for (int i = 0; i < n - 2; i++) {
int a, b; cin >> a >> b;
merge(a, b);
}
for (int i = 2; i <= n; i++) {
if (!isUnion(1, i)) {
cout << 1 << " " << i;
return 0;
}
}
return 0;
}