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

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

유니온-파인드(union-find) 문제이다.

주의할 것은 parent[i]와 getParent(i)를 구별하는 것이다.

parent[i] : i의 부모 노드(번호)

getParent(i) : i의 루트 노드(번호)

#include <bits/stdc++.h>
 
using namespace std;
 
int n, parent[300003];
 
int getParent(int x)
{
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}
 
void unionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
int main(void)
{
    int left, right;
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        parent[i] = i;
 
    for (int i = 0; i < n - 2; i++)
    {    
        scanf("%d %d", &left, &right);
        unionParent(left, right);
    }
 
    for (int i = 1; i <= n - 1; i++)
        if (getParent(i) != getParent(i + 1))
        {
            printf("%d %d\n", i, i + 1);
            return 0;
        }
 
    return 0;
}