Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Efficient approach of PRIMS Algorithm for finding MST
- //Time Complexity: O(nlogn) (used heap ds for keeping track of minimum value, brings down the
- //search complexity to logn)
- /*
- input:
- altered input || original input
- 6 9
- 0 1 5 || 1 2 5
- 0 2 4 || 1 3 4
- 0 3 6 || 1 4 6
- 1 2 2 || 2 3 2
- 2 3 1 || 3 4 1
- 1 4 9 || 2 5 9
- 2 4 3 || 3 5 3
- 3 5 7 || 4 6 7
- 4 5 10 || 5 6 10
- */
- /*
- output:
- 2 --- 1
- 0 --- 2
- 2 --- 3
- 2 --- 4
- 3 --- 5
- the MST created will be:
- 1
- |
- |4
- 2 | 1
- 2-----3-----4
- | |
- 3| |7
- | |
- 5 6
- total sum: 17
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- #define inf 2e18
- int MOD=1000000007;//998244353;
- const int nn=1000050;
- bool prime[nn]; //array to store precalculated primes till 10^6
- void cal_primes(){memset(prime,true,sizeof(prime)); for(int i=2;i<=sqrt(nn);++i){ if(prime[i]==true){ for(int j=i*i;j<=nn;j+=i){prime[j]=false;}}}}
- void solve(int t)
- {
- int testcases=t;
- while(t--)
- {
- int n,m;cin>>n>>m;
- vector<pair<int,int>> g[n];
- int x,y,wt;
- for(int i=0;i<m;i++){
- cin>>x>>y>>wt;
- g[x].push_back({y,wt});
- g[y].push_back({x,wt});
- }
- int parent[n],key[n];
- bool mstSet[n];
- memset(parent,-1,sizeof(parent));
- memset(mstSet,false,sizeof(mstSet));
- priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
- key[0]=0,parent[0]=(-1);
- pq.push({0,0});
- for(int i=0;i<n-1;i++){
- int u=pq.top().second;
- pq.pop();
- mstSet[u]=true;
- for(auto it:g[u]){
- int v=it.first;
- int weight=it.second;
- if(!mstSet[v] && weight<key[v]){
- parent[v]=u;
- pq.push({key[v],v});
- key[v]=weight;
- }
- }
- }
- for(int i=1;i<n;i++)
- cout<<parent[i]<<" -- "<<i<<endl;
- }
- }
- main()
- {
- auto start=chrono::system_clock::now();
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- freopen("error.txt","w",stderr);
- #endif
- ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- int t=1;
- // cin>>t;
- solve(t);
- }
- auto end=chrono::system_clock::now();
- chrono::duration<double> elapsed=end-start;
- // cout<<endl<<"Time taken: "<<elapsed.count()<<" sec";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement