1197. 최소 스패닝 트리

나는 크루스칼 알고리즘으로 mst를 구현하였다.

하지만, 이 소스에서는 개선점이 있다.

union-find 알고리즘을 사용해서 좀더 효율적으로 구현이 가능할 것 같다.  

#include<stdio.h>
#include<iostream>
using namespace std;

#define MAX_NUM 100010

int input[MAX_NUM][3];
int num;
int n = 0;
int m = 0;
void swap(int i ,int j) {
	int temp[3] = { input[i][0],input[i][1], input[i][2] };
	input[i][0] = input[j][0];
	input[i][1] = input[j][1];
	input[i][2] = input[j][2];
	input[j][0] = temp[0];
	input[j][1] = temp[1];
	input[j][2] = temp[2];
}
void quickSort(int first, int last)
{
	int pivot;
	int i;
	int j;
	int temp;

	if (first < last)
	{
		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i][2] <= input[pivot][2] && i < last)
			{
				i++;
			}
			while (input[j][2] > input[pivot][2])
			{
				j--;
			}
			if (i < j)
			{
				swap(i, j);
			}
		}

		swap(pivot, j);

		quickSort(first, j - 1);
		quickSort(j + 1, last);
	}
}
int kruskal() {
	int cycle_list[10001] = {0};
	int cost = 0;
	for (int i = 1; i <= n; i++)
		cycle_list[i] = i;
	int cycle_amount = 0;
	int i = 0;
	while (cycle_amount < n-1) {
		if (cycle_list[input[i][0]] != cycle_list[input[i][1]]) {
			if (cycle_list[input[i][0]] < cycle_list[input[i][1]]) {
				for (int h = 1; h <= n; h++) {
					if (cycle_list[input[i][1]] == cycle_list[h] && h != input[i][1]) {
						cycle_list[h] = cycle_list[input[i][0]];
					}
				}
				cycle_list[input[i][1]] = cycle_list[input[i][0]];
			}
			else {
				for (int h = 1; h <= n; h++) {
					if (cycle_list[input[i][0]] == cycle_list[h] && h != input[i][0]){
						cycle_list[h] = cycle_list[input[i][1]];
				}
			}
				cycle_list[input[i][0]] = cycle_list[input[i][1]];
			}
			cost += input[i][2];
			cycle_amount++;
		}
		i++;
	}
	return cost;
}
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &input[i][0], &input[i][1], &input[i][2]);
	}
	quickSort(0,m-1);
	printf("%d",kruskal());

	return 0;
}