# Cod sursa(job #2809120)

Utilizator Data 26 noiembrie 2021 00:25:45 Arbore partial de cost minim 100 cpp-64 done Arhiva educationala 3.14 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define MAX 100001

using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");

class Graf{
public:
//date membre
vector <pair<pair<int, int>, int> > A;

//nr muchii sol
int msol;
//muchiile solutie
vector <pair<int, int> > sol;
int mM, mN;
vector<int> parent;
vector<int> rank;
//static bool viz[MAX];

//constructor

Graf(int N, int M){
mN = N;
mM = M;
parent.resize(N+1);
rank.resize(N+1);

}

void CitireG(int M);

int Find(int x);
void Union(int x, int y);
void Kruskall();

};

bool ok(const pair<pair<int, int>, int>&x, const pair<pair<int, int>, int>&y){
//comparam al 2 lea parametru din perechile de tipul ((x,y),c) - care reprezinta costul
return (x.second < y.second);
}

void Graf:: CitireG(int M){

int x,y,c;

for(int i = 0; i < M; i++){

fin >> x >> y >> c;
A.push_back(make_pair(make_pair(x,y),c));
}
}

int Graf :: Find(int x){
//daca nu mai gasim tata pentru nodul curent
if( x == parent[x])
return x;

//mergem din tata in tata pana gasim nodul de start
return Find(parent[x]);
}

void Graf :: Union (int x, int y){
//gasim radacina/stramosul fiecarei componente pe care vrem sa le unim
int px = Find(x);
int py = Find(y);

if(rank[px] >= rank[py]){
//parintele subarborelui mai mic devine subarborele mare (Radacina sa)

parent[py] = px;
rank[px] += rank[py];
msol++;
}
else{

parent[px] = py;
rank[py] += rank[px];
msol++;
}
}

void Graf :: Kruskall(){

int C = 0; //costul total
int x,y;
//momentan n avem nicio muchie solutie
msol = 0;

//initializam vectorii parent si rank
for (int i = 1; i <= mN; i++)
parent[i] = i, rank[i] = 1;

//sortam vectorul de muchii crescator in fc de cost

sort(A.begin(), A.end(), ok);

//verificam muchiile pe rand
for(int i = 0 ; i < mM; i++){

//cautam "cel mai indepartat stramos" pentru ambele capete ale muchiei
x = Find(A[i].first.first);
y = Find(A[i].first.second);

//daca nu au "stramos" comun, atunci nu exista alt drum de la x la y in afara de muchia x-y
if(y != x){
//o adaugam in vect de sol
sol.push_back(make_pair(A[i].first.first, A[i].first.second));

//si punem muchia pe graful nostru actual
Union(A[i].first.first, A[i].first.second);

//adunam costul muchiei la costul tota
C+= A[i].second;
}
}

fout << C << "\n";
fout << msol <<"\n";

for(int i = 0; i < msol; i++){
fout << sol[i].first << " " << sol[i].second << "\n";

}

}

int main(){
int N, M;
fin >> N >> M;
Graf G(N,M);
G.CitireG(M);

G.Kruskall();

return 0;
}
``````