fork(1) download
copy 
  1. /* Author:- Mayank Pratap Singh
  2.  
  3.    2nd year, MNNIT
  4.    
  5. */   
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define ff first
  9. #define ss second
  10. #define pb push_back
  11. #define mp make_pair
  12.  
  13. #define MOD 1000000007
  14.  
  15. typedef long long ll;
  16. typedef long double ld;
  17.  
  18. const int INF=(int)(1e9);
  19. const ll INF64=(ll)(1e18);
  20. const ld EPS=1e-9;
  21. const ld PI=3.1415926535897932384626433832795;
  22.  
  23. const int N=100005;
  24.  
  25. vector<list<pair<int,int> > >adjList(N+1);
  26. vector<list<pair<int,int> > >spanning_tree(N+1);
  27. list<pair<int,int> >::iterator it;
  28. int parent[N+1];
  29. int level[N+1];
  30. int visited[N+1];
  31. int n,m;
  32.  
  33. priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >pq;
  34.  
  35. void prims(int start){
  36.  
  37.     int count=0,u=start;
  38.  
  39.     for(int i=1;i<=n;++i)
  40.     	visited[i]=0;
  41.  
  42.     while(count<n){
  43.  
  44.         it=adjList[u].begin();
  45.  
  46.         ++count;
  47.  
  48.         visited[u]=1;
  49.  
  50.         while(it!=adjList[u].end()){  // Adding edges to priority queue
  51.  
  52.             int v=it->ff;
  53.             int w=it->ss;
  54.             pq.push(mp(w,mp(u,v)));
  55.             ++it;
  56.         }
  57.  
  58.         while(!pq.empty()){
  59.  
  60.              int w=pq.top().ff;
  61.              int v1=pq.top().ss.ff;
  62.              int v2=pq.top().ss.ss;
  63.  
  64.              pq.pop();
  65.  
  66.              if(visited[v2]==1)
  67.                 continue;
  68.  
  69.              else{
  70.  
  71.                 spanning_tree[v1].pb(mp(v2,w));    // Pushing edge to spanning tree  
  72.                 u=v2;   // Go to terminal vertex of edge
  73.                 break;
  74.  
  75.              }  // else
  76.         }   // close to pq.empty()
  77.  
  78.     }  // close to while(count<n)
  79.  
  80. }
  81.  
  82. int main(){
  83.  
  84.     int v1,v2,w;
  85.  
  86.     scanf("%d %d",&n,&m);
  87.  
  88.     for(int i=1;i<=m;++i){
  89.  
  90.         scanf("%d %d %d",&v1,&v2,&w);
  91.         adjList[v1].pb(mp(v2,w));
  92.         adjList[v2].pb(mp(v1,w));
  93.     }
  94.  
  95.     prims(1);  // We can start from any vertex
  96.  
  97.     printf("Printing Spanning Tree\n");
  98.  
  99.     for(int i=1;i<=n;++i){
  100.  
  101.         it=spanning_tree[i].begin();
  102.  
  103.         //  printf("Hello\n");
  104.  
  105.         while(it!=spanning_tree[i].end()){
  106.  
  107.            printf("%d %d %d\n",i,it->ff,it->ss);
  108.  
  109.            ++it;    
  110.  
  111.         }
  112.  
  113.     }
  114.  
  115.  
  116.     return 0; 
  117.  
  118. }
Success #stdin #stdout 0s 4640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Printing Spanning Tree
https://ideone.com/1mgkx2
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!