1197 최소 스패닝 트리

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

집합 연산을 나타내는 유니온 파인드를 이용한 크루스칼 알고리즘으로 최소 스패닝 트리(Minimum Spanning Tree)를 구성한다. 그래프의 모든 간선을 저장하고 정렬한 다음 가중치가 작은것 부터 뽑는다. 간선의 양 끝 정점이 같은 집합인지 파인드 연산을 통해 확인하고 다른 집합이면 유니온 연산을 통해 같은 집합으로 합쳐주고 간선을 최소 스패닝 트리에 추가한다. 이 과정을 모든 정점이 같은 집합에 포함될 때 까지 반복하면 N-1개의 간선으로 구성된 최소 스패닝 트리가 완성된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct Edge
{
    int start,end,cost;
    bool operator < (const Edge &other) const { return cost<other.cost; }
};
 
int p[10001];
int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }
void Union(int x,int y) { p[Find(x)]=Find(y); }
 
int main()
{
    int n,m,ans=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    vector<Edge> a(m);
    for(int i=0;i<m;i++) scanf("%d %d %d",&a[i].start,&a[i].end,&a[i].cost);
    sort(a.begin(),a.end());
    for(int i=0;i<m;i++)
    {
        Edge e=a[i];
        int x=Find(e.start),y=Find(e.end);
        if(x!=y) Union(e.start,e.end),ans+=e.cost;
    }
    printf("%d\n",ans);
    return 0;
}