# Cod sursa(job #2695860)

Utilizator Data 14 ianuarie 2021 18:39:02 Arbore partial de cost minim 50 cpp-64 done Arhiva educationala 2.78 kb
``````#include<iostream>
#include<algorithm>
#include<fstream>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, cost;

class Edge  // muchie
{
public:
int source, destination, weight;
}edges[10000];

class Subset    // exista un lant intre toate elementele dintr-un subset
{
public:
int parent, rank;
};

bool cmp(Edge x, Edge y)    // comparam in functie de valoarea muchiei
{
return x.weight < y.weight;
}

void Read() // citire date graf
{
int i;
f>>n>>m;
for(i = 0; i < m; i++)
{
int x,y,z;
f>>x>>y>>z;
edges[i].source = x;
edges[i].destination = y;
edges[i].weight = z;
}
}

/*
void PrintEdges()   // print graf initial
{
int i;
cout<<"======= GRAF =======\n";
for(i = 0; i < m; i++)
cout<<edges[i].source<<" "<<edges[i].destination<<" "<<edges[i].weight<<'\n';
}
*/

int Find(Subset subsets[], int i)
{
if(subsets[i].parent != i)  // diferit de valoarea initiala
subsets[i].parent = Find(subsets, subsets[i].parent);    // path compression

return subsets[i].parent;
}

void Union(Subset subsets[], int x, int y)
{
int xSet = Find(subsets, x);
int ySet = Find(subsets, y);

if(subsets[xSet].rank < subsets[ySet].rank)     // nodul cu rank mai mic
subsets[xSet].parent = ySet;                // devine copilul nodului cu rank mai amre
else if (subsets[xSet].rank > subsets[ySet].rank)
subsets[ySet].parent = xSet;
else                                            // daca rank-urile sunt egale
{                                               // un nod va deveni parintele celulalt, rank-ul lui crescand cu 1
subsets[ySet].parent = xSet;
subsets[xSet].rank++;
}
}

void Kruskal(Edge edges[])
{
int count = 0, nr = 0;
Edge result[1000];
Subset subsets[1000];

sort(edges, edges + m, cmp);
for(int i = 0; i < n; i++)
{
subsets[i].parent = i;
subsets[i].rank = 0;
}

while(count < n - 1 && nr < m)
{
Edge next = edges[nr++];
int x = Find(subsets, next.source);
int y = Find(subsets, next.destination);

if(x != y)
{
result[count++] = next;
Union(subsets, x, y);
}
}

//cout<<"======= APM =======\n";

for(int i = 0; i < count; i++)
{
//cout<<result[i].source<<" "<<result[i].destination<<" -> "<<result[i].weight<<'\n';
cost += result[i].weight;
}
g<<cost<<'\n';
g<<count<<'\n';

for(int i = 0; i < count; i++)
g<<result[i].source<<" "<<result[i].destination<<'\n';

}

int main()

{