Cod sursa(job #3371493)

Utilizator Moriiandrei Morii Data 30 octombrie 2026 16:31:44
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;


int n,m;
struct elem{

  int st,dr,cost;


}x[400001];
int t[200001],r[200001];
bool comp(elem a,elem b)
{
      return a.cost < b.cost;
}

int find(int nod)
  {
      if(nod == t[nod])
        return nod;
      else return t[nod] = find(t[nod]);

  }
//int t[200001],r[200001];

void unire(int a,int b)
    {
        int p1 = find(a),p2 = find(b);
        if(r[p1] > r[p2])
           {
               t[p2] = p1;
               r[p1]++;

           }
        else{


              t[p1] = p2;
               r[p2]++;


        }

    }
  vector<pair<int,int>>xx;



signed main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
   cin >> n >> m;
   for(int i = 1;i<=n;++i)
    t[i] = i,r[i] = 1;
   for(int i = 1;i<=m;++i)
     {
         cin >> x[i].st >> x[i].dr >> x[i].cost;
     }
   sort(x+1,x+1+m,comp);
   int ans = 0;
      for(int i = 1;i<=m;++i)
      {
          int a = x[i].st,b=  x[i].dr;

          if(find(a)!=find(b))
             {
                 unire(a,b);
                 ans+=x[i].cost;
                 xx.push_back({a,b});
             }

      }

     cout << ans << '\n';
     cout << xx.size() << '\n';
     for(auto i : xx)
      cout << i.first << " " << i.second << '\n';




}