union find

알고리즘 문제를 풀다 보면 노드들 간의 집합이 존재하는 경우가 있다.

이때 해야할 일이 크게 두 가지 있다.

1. 두 노드가 같은 집합에 포함되어 있는지, 다른 집합에 있는지 확인하는 작업

2. 두 집합을 병합하는 작업

사람마다 위 과정을 처리하는 방법이 모두 다르고 시간복잡도도 다르다.

나 또한 무식하게 문제를 풀때는 O(n^2)이렇게 풀기도 했다. 

하지만 위 작업을 최적화한 자료구조로 union find가 있다.

(양교수님께서 알려주신 내용인데 당시에는 학점받기에 급급해 제대로 공부하지 못했다.)

그림파일 올리려고 했는데 귀찮아서 못올리겠다

http://blog.secmem.org/521

좋은 블로그가 있으니 여기를 참고하길..

void init(int n){ for(int i = 1; i <= n; i++){ par[i] = i; height[i] = 0; } } int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } void unite(int a, int b){ a = find(a); b = find(b); if(a == b) return; if(height[a]<height[b]){ par[a] = b; }else{ par[b] = a; if(height[a]==height[b]) height[a]++; } }