[백준 알고리즘] 1197번 최소 스패닝 트리 - C

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

#define MAX_SIZE 50

using namespace std;

typedef struct Edge {
        int v1;
        int v2;
        int value;

        Edge()
                : v1(0), v2(0), value(0)
        {
        }
        Edge(int a, int b, int c)
                : v1(a), v2(b), value(c)
        {
        }
}Edge;

bool compare(const Edge &a, const Edge &b) {
        return a.value < b.value;
}
/*
void print_vector(vector<Edge> &vec) {
        printf("%d\n", vec[0].v1);
}
*/

int findSet(int arr[], int a) {
        if(arr[a] == a) {
                return a;
        }
        return arr[a] = findSet(arr, arr[a]);
}
int findCycle(int arr[], int v1, int v2) {

        v1 = findSet(arr, v1);
        v2 = findSet(arr, v2);
        if(v1 == v2) {
                return 1;
        }
        return 0;
}

void margeSet(int arr[], int v1, int v2) {
        v1 = findSet(arr, v1);
        v2 = findSet(arr, v2);
        if(v1 < v2) {
                arr[v2] = v1;
        } else {
                arr[v1] = v2;
        }
}
int main(int argc, char* argv[]) {

        int v, edge, sum = 0;
        int vertex1, vertex2, value;

        scanf("%d %d", &v, &edge);
        vector<Edge> vec;
        for(int i = 0; i < edge; i++) {
                scanf("%d%d%d", &vertex1, &vertex2, &value);
                vec.push_back(Edge(vertex1, vertex2, value));
        }

        sort(vec.begin(), vec.end(), compare);

        int arr[v];
        for(int i = 1; i <= v; i++) { // 사이클 테이블
                arr[i] = i;
        }

        for(int i = 0; i < vec.size(); i++) {
                if(!findCycle(arr, vec[i].v1, vec[i].v2)) {
                        sum += vec[i].value;
                        margeSet(arr, vec[i].v1, vec[i].v2);
                }
        }
        printf("%d\n", sum);
        return 0;
}