[백준 1922] 네트워크 연결

문제 링크 => 1922번: 네트워크 연결 (acmicpc.net)

1922번: 네트워크 연결

 

최소 스패닝 트리 문제이다.

 

간선에 대한 정렬은 merge Sort를 이용하였다.

 

그리고 Union-Find 알고리즘을 이용하여 Cycle이 발생하지 않도록 확인해주었다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

struct Edge {
	int from, to, dist;
};

int parent[100001];
int N, M, cnt;
Edge E[100001], tmp[100001];

void mergeSort(int left, int right) {
	int l, mid, r, i; 

	i = l = left, mid = (left + right) / 2, r = (left + right) / 2 + 1;
	while (l <= mid && r <= right) {
		if (E[l].dist < E[r].dist)
			tmp[i++] = E[l++];
		else
			tmp[i++] = E[r++];
	}

	while (l <= mid) {
		tmp[i++] = E[l++];
	}
	while (r <= right) {
		tmp[i++] = E[r++];
	}

	for (i = left; i <= right; i++)
		E[i] = tmp[i];
	
	return;
}

void merge(int left, int right) {
	if (left == right)
		return;
	int mid = (left + right) / 2;
	merge(left, mid);
	merge(mid + 1, right);
	mergeSort(left, right);
}

void initialization(int N) {
	int i;
	for (i = 1; i <= N; i++)
		parent[i] = i;
}

int getParent(int parent[], int x) {
	if (parent[x] == x)
		return x;
	return parent[x] = getParent(parent, parent[x]);
}

void union_find(int parent[], int x, int y) {
	x = getParent(parent, x);
	y = getParent(parent, y);
	if (x < y)
		parent[y] = x;
	else
		parent[x] = y;
}

int is_union(int parent[], int x, int y) {
	x = getParent(parent, x);
	y = getParent(parent, y);
	if (x == y)
		return 1;
	return 0;
}

int main(void) 
{
	int i, from, to, dist, min_distance;

	scanf("%d", &N);
	scanf("%d", &M);
	for (i = 1; i <= M; i++) {
		scanf("%d %d %d", &from, &to, &dist);
		E[i].from = from, E[i].to = to, E[i].dist = dist;
	}
	
	merge(1, M);
	initialization(M);

	min_distance = 0;
	for (i = 1; i <= M; i++) {
		from = E[i].from, to = E[i].to, dist = E[i].dist;
		if (!is_union(parent, from, to)) {
			union_find(parent, from, to);
			min_distance += dist;
		}
	}

	printf("%d\n", min_distance);

	return 0;
}