[알고리즘] 유니온 파인드

이론정리

문제풀이

#include <iostream>
#include <vector>

using namespace std;
vector<int> uf;
//처음엔 원소 하나하나가 집합임
//0 - 같은 집합으로 합침 
//1 - 같은집합인지 확인

int find(int node) {
    if (uf[node] < 0) {
        return node;
    }
    return uf[node] = find(uf[node]);
}

void merge(int a, int b) {
    int parentA, parentB;
    parentA = find(a);
    parentB = find(b);
    if(parentA == parentB) return;
    
    if (uf[parentA] < uf[parentB]) { //a쪽 집합이 더 큼. 그러니까 b를 a부모쪽에 달아주기
        uf[parentB] = parentA;
        uf[parentA] = uf[parentA] - 1;
    }
    else if (uf[parentA] > uf[parentB]) { //반대
        uf[parentA] = parentB;
        uf[parentB] = uf[parentB] - 1;
    }
    else if (uf[parentA] == uf[parentB]) {
        uf[parentB] = parentA;
        uf[parentA] = uf[parentA] - 1;
    }
    return;
}

int main() {
    cin.tie(0);
	cin.sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    uf.assign(n+1, -1);
    
    for (int i = 0; i < m; i++) {
        int operation, a, b;
        cin >> operation >> a >> b;
        
        if (operation == 1) {
            if (find(a) == find(b)) cout << "YES" << '\n';
            else cout << "NO" << '\n';
        }
        else {
            merge(a, b);
        }
    }
    return 0;
}

• 이거 풀다가 똥을 너무 많이 쌌다,,ㅋㅎ
• 일단 merge 함수에서 실수로, 합칠거면 A집합의 루트node의 parent값을 B집합의 루트node값으로 바꿔줘야하는데, 그냥 A집합의 일반node의 parent값만 홀라당 바꿔줘서 틀렸었다. 집합전체를 다 옮겨야지 왜 하나만 옮기니,,!!!
• 저걸 고친 후에는 메모리 초과가 발생했는데, 알고보니까 같은 집합일 경우에는 명령 무시하고 바로 return해줘야했는데 그걸 안했다. 알아서 아무일 안일어나겠거니 하고 안적었었는데, 저거 처리안하면 무한루프가 발생한다,,^^,,