Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<cstdio>
- #include <vector>
- #include <fstream>
- #include <queue>
- #include <map>
- using namespace std;
- #define MAX_N 101
- #define MAX_M 101
- /*
- minimum spanning tree kruskal
- 6 8
- 0 1 1
- 0 2 3
- 2 1 3
- 2 3 1 1 6
- 1 3 1 (0)------(1)-------(5)
- | / | |
- 3 4 4 | / | |
- 1 5 6 3 | 3/ | 1 | 2
- 4 5 2 | / | |
- | / | |
- | / | |
- (2)------(3)------(4)
- 1 4
- */
- /*
- MST
- 1
- (0)------(1) (5)
- | |
- | |
- | 1 | 2
- | |
- | |
- | |
- (2)------(3)------(4)
- 1 4
- */
- int m,n,wt=0;
- struct Set{
- int parent, rnk;
- };
- struct Edge{
- int u, v,w;
- bool operator<(const Edge& rhs) const { //sort by weight
- return w > rhs.w;
- }
- };
- Set S[MAX_N];
- Edge E[MAX_M];
- priority_queue<Edge> q; //minheap data structure
- vector<pair<int,int>> mstEdge;
- queue<pair<int, int>>e;
- void read_graph() {
- for (int i = 0; i <m ; ++i) {
- Edge temp;
- scanf("%d%d%d",&temp.u, &temp.v, &temp.w);
- q.push(temp);
- }
- }
- void make_set(){
- for(int i=0; i<n; i++){
- S[i].parent = i;
- S[i].rnk = 0;
- }
- }
- int find_set(int x){
- if(S[x].parent !=x)
- return S[x].parent = find_set(S[x].parent);
- return x;
- }
- void link(int u, int v){
- if(S[u].rnk > S[v].rnk){
- S[v].parent = u;
- }
- else{
- S[u].parent = v;
- if(S[u].rnk ==S[v].rnk)
- S[v].rnk++;
- }
- }
- void ds_union(int x, int y, int w){
- int u = find_set(x);
- int v = find_set(y);
- if(u != v) {
- // cout<<"U : "<<x<<", V : "<<y<<", W : "<<w<<endl;
- wt +=w;
- mstEdge.push_back(make_pair(x,y));
- link(u, v);
- }
- }
- void kruskal() {
- make_set();
- while(!q.empty()){
- Edge temp = q.top();
- // cout<<temp.u<<" "<<" "<<temp.v<<" "<<temp.w<<endl;
- ds_union(temp.u, temp.v,temp.w);
- q.pop();
- }
- }
- void print_mst() {
- cout<<"------Printing MST------\n";
- for (int i = 0; i <mstEdge.size() ; ++i) {
- pair<int, int> temp = mstEdge[i];
- cout<<temp.first<<" "<<temp.second<<endl;
- }
- cout<<"MST cost : "<<wt<<endl;
- }
- int main() {
- freopen("graph.txt", "r", stdin);
- cin>>n>>m;
- read_graph();
- kruskal();
- print_mst();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement