Algorithms/classicalAlgos/kruskalsAlgorithm/kruskals.c at master · deutranium/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 1000005
#define I 10000000005

typedef long long int ll;
typedef struct Node
{
    ll cost;
    ll vertex1;
    ll vertex2;
} Node;
int comparator(const void *a, const void *b)
{
    return ((*(Node *)a).cost - (*(Node *)b).cost);
}
ll parent(ll set[], ll i)
{
    if (set[i] == i)
        return i;
    else
    {
        set[i] = parent(set, set[i]);
        return set[i];
    }
}
void setUnion(ll set[], ll a, ll b)
{
    a = parent(set, a);
    b = parent(set, b);
    if (a != b)
        set[b] = a;
}
void initSet(ll set[], ll v)
{
    for (ll i = 0; i < v; i++)
        set[i] = i;
}
long long int kruskals(Node m[], ll e, ll n)
{
    long long int sum = 0;
    ll set[N];
    initSet(set, n);
    ll j = 0;
    ll counter = 0;
    qsort(m, e, sizeof(Node), comparator);
    while ((j < n - 1) && (counter < e))
    {
        ll x = m[counter].vertex1, y = m[counter].vertex2;

        if ((parent(set, x) != parent(set, y)) && (counter < e))
        {
            sum += m[counter].cost;
            setUnion(set, x, y);
            j++;
        }
        counter++;
    }
    return sum;
}
int main()
{
    ll n = 0, X = 0;
    scanf("%lld %lld", &n, &X);
    Node edges[N];
    assert(edges);
    for (ll i = 0; i < X; i++)
    {
        scanf("%lld %lld %lld", &edges[i].vertex1, &edges[i].vertex2, &edges[i].cost);
    }
    printf("%lld\n", kruskals(edges, X, n));
    return 0;
}