크루스칼1 최소 스패닝 트리 크루스칼 O(ElogE) 필요한 것: union-find (merge 병합성공여부 반환) 간선구조체 - 가중치 기준으로 오름차순 정렬하기 위함. int uf[100001]; int find(int a) { if (uf[a] < 0) return a; return uf[a] = find(uf[a]); } bool merge(int a, int b) { a = find(a); b = find(b); if (a == b) return false; uf[a] = b; return true; } struct Edge { int u, v, w; Edge(int u1, int v1, int w1) : u(u1), v(v1), w(w1) {} bool operator < (const Edge& O) const { re.. 2019. 8. 18. 이전 1 다음