[Baekjoon,1197] 최소 스패닝 트리

간선의 가중치 합이 최소인 스패닝 트리를 만들어야 한다. 이를 위해서 나는 크루스칼의 알고리즘을 이용했다. 크루스칼 알고리즘은 아주 간단하다. 선택 후 사이클이 되지 않는 간선을 선택한다. 이때 간선의 가중치가 작은 것부터 차례로 선택한다. 이를 최소 스패닝 트리가 될 때까지 반복한다.

여기서 중요한 것은 사이클이 되지 않는 간선만을 선택을 하는 것이다. 이는 상호 배타적 집합 자료구조를 이용하면 간단하다. 두 정점이 이미 같은 집합에 속해있다면 이들을 이을 경우 사이클이 된다. 따라서 두 정점이 다른 집합에 있는 경우에만 이어나가면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const int MAX_V=10000;
const int INF=INT_MAX;

struct DisjointSet
{
    vector<int> parent,rank;
    DisjointSet(int v) : parent(v), rank(v,1)
    {
        for(int i=0;i<v;++i)
            parent[i]=i;
    }
    // u가 속한 집합을 찾는다. 
    int find(int u)
    {
        if(parent[u]==u)
            return u;
        return parent[u]=find(parent[u]);
    }
    bool merge(int u, int v)
    {
        u=find(u); v=find(v);
        if(u==v) return false;
        // u의 트리가 rank가 더 깊게 한다. 
        if(rank[u]<rank[v]) swap(u,v);
        parent[u]=v;
        // 두 트리의 rank가 같은 경우 
        if(rank[u]==rank[v])
            ++rank[u];
        return true;
    }
};

int V,E;
vector<pair<int,int> > adj[MAX_V];

int getMinWeight()
{
    // <간선의 가중치, 간선 인덱스>
    vector<pair<int,pair<int,int> > > edges;
    for(int here=0;here<V;++here)
        for(int i=0;i<adj[here].size();++i)
        {
            int there=adj[here][i].first;
            int cost=adj[here][i].second;
            edges.push_back(make_pair(cost,make_pair(here,there)));
        }
    sort(edges.begin(),edges.end());
    
    DisjointSet set(V);
    int ret=0;
    for(int i=0;i<edges.size();++i)
    {
        int cost=edges[i].first;
        int u=edges[i].second.first;
        int v=edges[i].second.second;
        if(set.merge(u,v))
            ret+=cost;
    }
    return ret;
}

int main()
{
    cin>>V>>E;
    for(int i=0;i<E;++i)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        --a;--b;
        adj[a].push_back(make_pair(b,c));
    }
    cout<<getMinWeight()<<endl;
    return 0;
}