[백준1997]최소 신장 트리

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

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

풀이

최소신장트리의 엣지 중심의 알고리즘이다.
우선순위큐로 정점들을 최솟값으로 정렬 후

유니온&파인드 알고리즘을 이용하여
부모가 같지 않다면 노드 연결을하여 n-1까지 수행하는 매커니즘이다.

void union_set(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a != b)
	{
		parent[b] = a;
	}
}
int find(int a)
{
	if (a ==parent[a])
	{
		return a;
	}
	else
	{
		return parent[a] = find(parent[a]);
	}

핵심인 부분인 유니온 파인드이다. 먼저 parent 배열을 i로 초기화 후

while (use < n - 1)
{
	Edge now = myque.top();
	myque.pop();
	if (find(now.s) != find(now.e))
	{
		union_set(now.s,now.e);
		use++;
		result += now.v;
		
	}
}

n-1까지 유니온 파인드를 실행한다. 유니온 파인드로 최솟값으로 정렬되어 있으니 정렬은하지 않아도 된다.
find로 연결되어 있는지 보고 연결되어 있지 않으면 union 실행
거기서 다시 재귀적으로 탐색하고 트리를 구성한다.

코드```

#include
#include
#include
#include
#include
#include
#include
#include
#include<limits.h>
using namespace std;
vectorparent;
typedef struct Edge {
int s, e, v;
bool operator > (const Edge& temp)const{
return v > temp.v;
}
}Edge;

void union_set(int a, int b);
int find(int a);
priority_queue<Edge, vector, greater> myque;
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;

cin >> n >> m;
for (int i = 0; i < m; i++)
{
	int a, b, c;
	cin >> a>> b>> c;
	myque.push(Edge{ a,b,c });
}
parent.resize(n + 1);
for (int i = 0; i <= n; i++)
{
	parent[i] = i;
}

int use = 0;
int result = 0;
while (use < n - 1)
{
	Edge now = myque.top();
	myque.pop();
	if (find(now.s) != find(now.e))
	{
		union_set(now.s,now.e);
		use++;
		result += now.v;
		
	}
}
cout << result;

}

void union_set(int a, int b)
{
a = find(a);
b = find(b);
if (a != b)
{
parent[b] = a;
}
}
int find(int a)
{
if (a ==parent[a])
{
return a;
}
else
{
return parent[a] = find(parent[a]);
}
}코드를 입력하세요