Se dă un graf neorientat ponderat conex cu n vârfuri și m muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim.

Date de intrare

Fișierul de intrare kruskal.in conține pe prima linie numerele n m, iar următoarele linii câte un triplet i j c, cu semnificația: există muchia (i j) și are costul c.

Date de ieșire

Fișierul de ieșire kruskal.out va conține pe prima linie costul arborelui de cost minim determinat, iar pe următoarele n-1 linii câte o pereche de numere i j, cu semnificația că muchia (i j) aparține arborelui parțial de cost minim determinat.

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unei muchii va fi mai mic decât 1000

Exemplu

kruskal.in

7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5

kruskal.out

12
3 4
4 5
1 2
2 5
2 6
2 7

SOLUTIE

#include <iostream>
#include <fstream>
#define INFINIT 1000000000
using namespace std;

ifstream fin("kruskal.in");
ofstream fout("kruskal.out");

struct muchie{
    int i,j,cost;
};

int n , m , t[105];

muchie x[5000];
int v[5000];

int main()
{
    fin >> n >> m;
    
    for(int i = 0 ; i < m ; ++i)
        fin >> x[i].i >> x[i].j >> x[i].cost;
    
    for(int i = 0 ; i < m - 1; i ++)
        for(int j = i + 1 ; j < m ; ++j)
            if(x[i].cost > x[j].cost)
            {
                muchie aux = x[i];
                x[i] = x[j];
                x[j] = aux;
            }
    for(int i =1 ; i <= n ; ++i)
        t[i] = i;
    int S = 0, cnt = 0;
    for(int i = 0 ; i < m && cnt < n ; i ++)
        if(t[x[i].i] != t[x[i].j])
        {
            v[i] = 1;
            S += x[i].cost;
            int ai = t[x[i].i], aj = t[x[i].j];
            for(int j =1 ; j <= n ; ++j)
                if(t[j] == aj)
                    t[j] = ai;
        }
    fout << S << "\n";
    for(int i = 0 ; i < m ; ++i)
        if(v[i] == 1)
            fout << x[i].i << " " << x[i].j << "\n";
    return 0;
}