블로그 이사 중입니다 >> gumgood.github.io

C++11 DFSC++11 Disjoint set 요소(Component) : 원 그래프 G에서 node와 edge가 서로 겹치지 않는(independent) 부그래프를 'G의 요소'라고 한다.연결요소(Connected Component) : 요소 내 모든 node쌍에 대해 경로가 존재하는 부그래프 S를 'G의 연결요소'라고 한다. 1. 전체 그래프에 대해 몇 번 DFS를 돌았는지 카운트한다. DFS의 시간복잡도는 O(V+E)이므로 전체 시간복잡도는 O(n+m) 2. Disjoint set이 몇 개인지 카운트한다. Union-Find 시간복잡도는 O(1), 초기화 O(n) 카운트하는데 O(n)이므로 전체 시간복잡도는 O(n) *입력 O(m)인건 무시

- Disjoint-set(분리집합) : 교집합이 존재하지 않는 두 집합- 서로 구분되어야 하는 data 집합을 다룰 때 유용하게 쓰인다. 1. 연산 Init() : n개의 element가 각각의 집합에 포함되어 있도록 초기화 Union() : 두 element x, y가 주어질 때, 이 둘이 속한 두 집합을 하나로 합친다. Find() : 어떤 element x가 주어질 때, 이 element가 속한 set의 root를 반환한다. 2. 구현 Find()연산은 각 element의 대표값을 재귀적으로 갱신해나간다. (경로압축) C++11 3. 시간복잡도 Find() (= Union())의 시간복잡도는 경로압축시 O(ack(n))이다. ack(n) : Ackermann function으로, 거의 에 근사한다..