[백준][C++] 1922: 네트워크 연결

문제

1922번: 네트워크 연결

풀이

최소 스패닝 트리, 크루스칼 알고리즘 문제이다.

 

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

최소 스패닝 트리, 크루스칼 알고리즘의 기본 문제로 위의 문제와 풀이가 같다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct
{
    int v1;
    int v2;
    int dist;
}edge;

int parent[1001];

bool compare(edge a, edge b)
{
    return a.dist < b.dist;
}

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

bool cycle(int n1, int n2)
{
    n1 = getParent(n1);
    n2 = getParent(n2);

    return n1 == n2;
}

void Union(int n1, int n2)
{
    int p1 = getParent(n1);
    int p2 = getParent(n2);

    if (p1 < p2)
    {
        parent[p2] = p1;
    }
    else
    {
        parent[p1] = p2;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<edge> edges;
    for (int i = 0; i < M; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;

        edges.push_back({ a, b, c });
    }

    sort(edges.begin(), edges.end(), compare);
    for (int i = 1; i <= N; ++i)
    {
        parent[i] = i;
    }

    int answer = 0;
    for (auto edge : edges)
    {
        if (!cycle(edge.v1, edge.v2))
        {
            Union(edge.v1, edge.v2);
            answer += edge.dist;
        }
    }
    
    cout << answer;

    return 0;
}