Árvore Geradora Máxima (examplo)

AG_MAX.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100;

pair <int, pair <int,int> > p[MAX];
int id[MAX], vertices, arestas, arvores, pesoMAX;


void iniciarVertices(int n){
    for(int i = 1; i <= n; i++)
        id[i] = i;
       
}

int noVet(int x){
    while(id[x] != x){
        id[x] = id[id[x]];
        x = id[x];
       
    }
    return x;
}

//Depois que verificou que n\E3o existe ciclo, junta-se os n\F3s 
void ligarNo(int a, int b){ 
    a = noVet(a);
    b = noVet(b);
    id[a] = b;
   
}

int main(){
	//ler a entrada
	printf("Informe a quantidade de Arvores:");
    scanf("%d", &arvores);
    while(arvores--){
    	printf("Informe a quatidade de Arestas:");
        scanf("%d", &arestas);
        printf("Informe a quatidade de Vertices:");
        scanf("%d", &vertices);
        for(int i = 0; i < arestas; i++){
        
        		   int a,b,c;
            scanf("%d %d %d", &c, &a, &b);
            p[i] = make_pair(c, make_pair(a,b)); //montar os pares das arestas
		
         
        }
        iniciarVertices(vertices);//inicializa os vertices
        sort(p,p+arestas); //ordenar as arestas
        pesoMAX = 0;
        for(int i = arestas-1; i > -1; i--){ //comeca do final do vetor, onde temos a aresta mais pesada
            int x = p[i].second.first;
            int y = p[i].second.second;
            int cost = p[i].first;
           
            if(noVet(x) != noVet(y)){//verifica se tem ciclo, se os nos pertecente a arvore
                pesoMAX += cost;
                ligarNo(x,y);
            }
        }
        printf("Peso MAXIMO \E9:%d\n",pesoMAX); //imprime o peso 
    }
    return 0;
}