[백준] 1197 최소 스패닝 트리

백준1197링크

입력

정점의 개수 V(1 ≤ V ≤ 10,000), 간선의 개수 E(1 ≤ E ≤ 100,000)
A번 정점과 B번 정점이 가중치 C인 간선으로 연결
C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력

풀이

신장 트리란, 그래프의 모든 노드를 포함하면서 사이클 X
최소 신장 트리(Minimum Spanning Tree)는 신장 트리 중 비용이 최소

크루스칼 알고리즘(Kruskal Algorithm)
1) 간선의 비용에 따라 오름차순 정렬
2) 간선을 하나씩 확인하면서 사이클을 만드는지 확인
-> 사이클이 발생하지 않은 경우, MST에 추가 및 비용 더해주기
3) 모든 간선에 대해 2)번 반복

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define MAXV 10001
int V, E;
vector<pair<int, int>> g; //시작노드, 종료노드 저장
vector < pair<long long, int>> cost; //간선별 비용 저장
long long total = 0;

int parent[MAXV]; //각 노드의 루트 노드 저장

int findParent(int x) { //노드별 루트노드 찾기
	if (parent[x] == x) {
		return x;
	}

	return parent[x] = findParent(parent[x]);
}

void Union(int x, int y) { //노드 합집합 연산
	x = findParent(x);
	y = findParent(y);

	if (x == y)
		return;

	if (x < y) {
		parent[y] = x;
		findParent(y);
	}
	else {
		parent[x] = y;
		findParent(x);
	}
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> V >> E;

	int a, b;
	long long c;
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		g.push_back(make_pair(a,b));
		cost.push_back(make_pair(c, i));
	}

	sort(cost.begin(), cost.end()); //오름차순으로 비용 정렬

	for (int i = 1; i <= V; i++) {
		parent[i] = i; //parent 배열 자기자신으로 초기화
	}

	for (int i = 0; i < cost.size(); i++) {
    //루트노드가 같지 않은경우(사이클 발생 X) 합집합
		if (findParent(g[cost[i].second].first) != findParent(g[cost[i].second].second)) {
			Union(g[cost[i].second].first, g[cost[i].second].second);
			total += cost[i].first;
		}
	}

	cout << total << "\n";
	return(0);
}