Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include<iostream>
- // #include<algorthem>
- #include<bits/stdc++.h>
- using namespace std;
- #define MX 100
- struct edgeStructure
- {
- int u;
- int v;
- int w;
- };
- bool operator < (edgeStructure lhs , edgeStructure rhs)
- {
- return lhs.w < rhs.w;
- }
- bool cmp(const edgeStructure &lhs ,const edgeStructure &rhs)
- {
- if(lhs.u != rhs.u)
- return lhs.u < rhs.u;
- else return lhs.w < rhs.w;
- }
- int parent[MX];
- int rankParent[MX];
- vector<edgeStructure> edgeVector;
- void makeSet(int n)
- {
- for(int i=0;i<n;i++){
- parent[i]=i;
- rankParent[i]=0;
- }
- }
- int findParent(int x)
- {
- if(x!=parent[x])
- return parent[x]=findParent(parent[x]);
- else return x;
- }
- void unionSet(int x,int y)
- {
- int xRoot =findParent(x);
- int yRoot =findParent(y);
- if(xRoot==yRoot) return;
- if(rankParent[xRoot]<rankParent[yRoot])
- parent[xRoot]=yRoot;
- else if(rankParent[xRoot]>rankParent[yRoot])
- parent[yRoot]=xRoot;
- else {
- parent[yRoot]=xRoot;
- rankParent[xRoot]++;
- }
- }
- int kruskal(int n)
- {
- makeSet(n);
- sort(edgeVector.begin(),edgeVector.end());
- int sz = edgeVector.size();
- int ans=0;
- for(int i=0;i<sz;i++){
- if(findParent(edgeVector[i].u)!=findParent(edgeVector[i].v))
- {
- /// union
- unionSet(parent[edgeVector[i].u],parent[edgeVector[i].v]);
- //cout<<edgevector[i].u <<" "<<edgevector[i].v<<endl;
- ans+=edgeVector[i].w;
- }
- }
- return ans;
- }
- int main()
- {
- int vertex,edge;
- cin>>vertex>>edge;
- for(int i=0;i<edge;i++)
- {
- edgeStructure e;
- cin>>e.u>>e.v>>e.w;
- edgeVector.push_back(e);
- }
- cout<<"MST Cost "<<kruskal(vertex)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement