반응형 분리집합1 [코드조각] union-find (분리집합) python에서 분리집합을 하기 위한 find 함수와 union함수. 둘 다 최악의 경우 시간복잡도 O(n)을 기록한다 # P[i]는 i가 속한 집합의 대표값이 담겨있다. def find(n): if P[n] == n: return n P[n] = find(P[n]) return P[n] def union(u, v): u = find(u) v = find(v) if u == v: return if u != v: P[v] = u 2021. 9. 13. 이전 1 다음 반응형