백준 1197

https://www.acmicpc.net/problem/1197

이 문제의 경우 최소 신장트리를 만들어 내는 문제이다 모든 정점들을 이었을 때 각 간선들의 최소가 되는 트리를 최소 신장트리라고 한다  이문제의 경우 내가 트리의 크루스칼 알고리즘을 이용해서 풀었다

크루스칼 알고리즘은 
1. 각 경로들의 cost 값으로 오름차순 정렬 한다
2. 각 경로들의 vertex 간 비교해서 각 vertex들이 이어진 경로의 root와 비교해서 서로 다르면 잇고 아니면 연결하지 않는다
3. 2의 과정을 반복한 후 Cost의 값을  도출한다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[10001] = { 0, };

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int  v, e,cost;
	cost = 0;
	cin >> v >> e;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < e; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		inputData.push_back({ tmp3,{tmp1,tmp2} });
	}

	sort(inputData.begin(), inputData.end());
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}

	for (int i = 0; i<inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
		}
	}
	cout << cost;
}