Union and Find in C++

Union and Find를 활용하여, 같은 사슬 내에 있는 지를 확인하는 코드

숫자 n개와, 숫자쌍의 갯수 m이 주어진다.
숫자를 통해 연결이 되면 한 사슬이라고 칭한다.
같은 사슬이면 YES, 아니라면 NO를 출력한다.

#include <iostream>

using namespace std;

int n, m, a, b, res_a, res_b;
int unf[1001];

int Find(int v) {
    if (v == unf[v]) return v;
    else return unf[v] = Find(unf[v]);		// 메모이제이션
}

int Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) unf[a] = b;
}

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {		// unf 배열 초기화
        unf[i] = i;
    }
    for (int i=1; i<=m; i++) {
        int a, b;
        cin >> a >> b;
        Union(a, b);
    }

    cin >> a >> b;

    res_a = Find(a);
    res_b = Find(b);
    if(res_a == res_b) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

메모이제이션을 통해, 다음 연산시 연산의 절차를 줄일 수 있다.

• Find : 같은 사슬인지를 확인
• Union : 사슬을 형성

ex)
9 7

1 2
2 3
3 4
4 5
6 7
7 8
8 9

3 8

9 7

1 2
2 3
3 4
4 5
6 7
7 8
8 9

1 4