Algorithm/상호 배타적 집합
-
Union-Find algorithmAlgorithm/상호 배타적 집합 2020. 1. 30. 01:57
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 //최적화된 상호 배타적 집합의 구현 //트리를 이용해 상호 배제적 집합을 구현한다 struct OptimizedDisjointSet { vector parent, rank; OptimizedDisjointSet(int n) : parent(n), rank(n, 1) { for(int i = 0; i rank[v]) swap(u, v); //이제 rank[v]가 항상 rank[u]이상이므로 u를 v의 자식으로 넣는다 parent[u] = v; if(rank[u] == rank[v]) ++rank[v]; } }; Colored by Color Scripter cs Un..