| 464 | } |
| 465 | |
| 466 | void kruskalsAlgo(){ |
| 467 | int n,m; |
| 468 | cin>>n>>m; |
| 469 | vector<node>edges; |
| 470 | for(int i=0;i<m;i++){ |
| 471 | int u,v,wt; |
| 472 | cin>>u>>v>>wt; |
| 473 | edges.push_back(node(u,v,wt)); |
| 474 | } |
| 475 | |
| 476 | sort(edges.begin(),edges.end(),comp); |
| 477 | vector<int>parent(n); |
| 478 | vector<int>rank(n,0); |
| 479 | |
| 480 | for(int i=0;i<n;i++){ |
| 481 | parent[i]=i; |
| 482 | } |
| 483 | |
| 484 | int cost=0; |
| 485 | vector<pair<int,int>>mst;//minimum spanning tree |
| 486 | for(auto it : edges){ |
| 487 | if(findpair(it.u,parent) !=findpair(it.v,parent)){ |
| 488 | cost+=it.wt; |
| 489 | mst.push_back({it.u,it.v}); |
| 490 | unionn(it.u,it.v,parent,rank); |
| 491 | } |
| 492 | } |
| 493 | |
| 494 | cout<<cost<<endl; |
| 495 | } |
| 496 | |
| 497 | void bridgeInGraph(int node,int parent,int& timer,vector<int>&vis,vector<int>&low,vector<int>&in,vector<int>arr[]){ |
| 498 | vis[node]=1; |