fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct edge {
  4.     int u, v;
  5.     int w;
  6. };
  7. const int maxn = 1001;
  8. int n,m;
  9. int parent[maxn], sz[maxn];
  10. vector<edge> canh;
  11. void make_set(){
  12.     for(int i = 1;  i <= n ; i++){
  13.         parent[i] = i;
  14.         sz[i] = 1;
  15.     }
  16. }
  17.  
  18. int find(int v){
  19.     if(v == parent[v]) return v;
  20.     return parent[v] = find(parent[v]);
  21. }
  22.  
  23. bool Union(int a,int b){
  24.     a = find(a);
  25.     b = find(b);
  26.     if(a == b) return false;
  27.     if(sz[a] < sz[b]) swap(a,b);
  28.     parent[b] = a;
  29.     sz[a] + sz[b];
  30.     return true;
  31. }
  32. void inp(){
  33.     cin >> n >> m ;
  34.     for(int i = 0 ; i < m ; i++){
  35.         int x,y,w;
  36.         cin >> x >> y >> w;
  37.         edge e;
  38.         e.u = x;
  39.         e.v = y;
  40.         e.w = w;
  41.         canh.push_back(e);
  42.     }
  43. }
  44. bool cmp(edge a, edge b){
  45.     return a.w < b.w;
  46. }
  47. void kruskal(){
  48.     // Tạo cây khung cực tiểu rỗng
  49.     vector<edge> mst;
  50.     int d = 0 ;
  51.     // Sort danh sách cạnh theo chiều dài tăng dần
  52.     sort(canh.begin() , canh.end(),cmp);
  53.     // BƯớc 3 : Lặp;
  54.     for(int i = 0 ; i < m ; i++){
  55.         if(mst.size() == n - 1) break;
  56.         edge e = canh[i]; // Chọn cạnh e là cạnh nhỏ nhất
  57.         if(Union(e.u,e.v)){
  58.             mst.push_back(e);
  59.             d +=e.w;
  60.         }
  61.     }
  62.     // Trả về kết quả
  63.     if(mst.size() != n - 1){
  64.         cout << "Đồ thị không liên thông !\n";
  65.     }
  66.     else{
  67.         cout << "MST : " << d << endl;
  68.         for(auto it : mst){
  69.             cout << it.u << " " << it.v << " " << it.w << endl;
  70.         }
  71.     }
  72. }
  73. int main(){
  74.     inp();
  75.     make_set();
  76.     kruskal();
  77. }
  78.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Đồ thị không liên thông !
https://ideone.com/NB08qn
Kruskal
language:
C++ (gcc 8.3)
created:
18 days ago
visibility:
public

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!