최소 스패닝 트리

크루스칼 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 { return w < O.w; }
};

int main() {
	int n, m;
	Edge e[1000000];
	fill(uf, uf + n, -1);
	sort(e, e + m); //가중치 기준 정렬

	int rst = 0, cnt = 0;
    //"MST 뽑기"
	for (int i = 0; ; i++) {
		if (merge(e[i].u, e[i].v)) { //양 끝점이 연결 돼있지 않은 간선에 대해서만
			rst += e[i].w;
			if (++cnt == n - 1) break; //n-1개의 간선을 뽑으면 종료
		}
	}

	cout << rst << '\n';
}

 

<+>

모든 간선을 힙에다 넣고 빼주는 '프림' 알고리즘도 O(ElogE)