[백준 1197] 최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

mst 구현 문제

크루스칼 알고리즘을 사용하여 풀었다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct s
{
  int a, b, cost;
};

int parent[10001];
vector<s> vs;
int v, e;
bool cmp(const s &t1, const s &t2)
{
  return t1.cost < t2.cost;
}

int find_parent(int node)
{
  if (parent[node] == node)
    return node;

  return parent[node] = find_parent(parent[node]);
}

void union_parnet(int n1, int n2)
{
  int np1 = find_parent(n1);
  int np2 = find_parent(n2);

  if (np1 < np2)
    parent[np2] = np1;
  else
    parent[np1] = np2;
}

bool is_cycle(int n1, int n2)
{
  if (find_parent(n1) == find_parent(n2))
    return true;
  else
    return false;
}

int main(void)
{
  scanf("%d%d", &v, &e);

  for (int i = 1; i <= v; i++)
  {
    parent[i] = i;
  }

  for (int i = 1; i <= e; i++)
  {
    int e1, e2, c;
    scanf("%d%d%d", &e1, &e2, &c);
    vs.push_back({e1, e2, c});
  }

  sort(vs.begin(), vs.end(), cmp);
  int res = 0;
  for (int i = 0; i < vs.size(); i++)
  {
    if (!is_cycle(vs[i].a, vs[i].b))
    {
      res += vs[i].cost;
      union_parnet(vs[i].a, vs[i].b);
    }
  }

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

  return 0;
}