Skip to content

Instantly share code, notes, and snippets.

@lsiddiqsunny
Last active September 4, 2017 19:32
Show Gist options
  • Save lsiddiqsunny/edd77b8f7f0f89f93f59a105f3cea75d to your computer and use it in GitHub Desktop.
Save lsiddiqsunny/edd77b8f7f0f89f93f59a105f3cea75d to your computer and use it in GitHub Desktop.
Krushkal algorithm implementation for Minimum spanning tree
#include<bits/stdc++.h>
using namespace std;
#define mx 500005
int id[mx],n,m;
pair <long long, pair<int, int> > p[mx];
void initialize()
{
for(int i = 0; i < mx; ++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
initialize();
for(int i = 0; i < k; ++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
{
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
p[i]=make_pair(t,make_pair(x,y));
}
sort(p, p + k);
long long cost=kruskal(p);
printf("%d",cost);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment