const int maxVertices = 50;
 
/*******************************************
 *              Equiv                      *
 *******************************************
 * Equiv is a structure type that holds a  *
 * pointer to an array of integers and an  *
 * integer of the size of that array.      *
 *******************************************/
struct Equiv
{
	int* arrayIntegers;
    int arraySize;
};
 
bool together(Equiv& e, int x, int y);
void combine(Equiv& e, int x, int y);

#include <iostream>
#include <fstream>
#include "equiv.h"
 
/**********************************************
 *               together                     *
 **********************************************
 * together returns true if x and y are in the*
 * same set as object e.                      *
 **********************************************/
bool together(Equiv& e, int x, int y)
{
	bool sameX = false;
	bool sameY = false;
 
	for(int i = 0; i < e.arraySize; i++)
	{
		if(e.arrayIntegers[i] == x)
			sameX = true;
		if(e.arrayIntegers[i] == y)
			sameY = true;
		if(sameX && sameY)
			break;
	}
	return (sameX && sameY);
}
 
/**********************************************
 *               combine                      *
 **********************************************
 * combine puts x and y together by combining *
 * the two into the same set.                 *
 **********************************************/
void combine(Equiv& e, int x, int y)
{
	if(together(e, x, y))
		return;
 
	bool switchX = false;
	bool switchY = false;
 
	if(e.arraySize > 0)
	{
		for(int i = 0; i < e.arraySize; i++)
		{
			if(x == e.arrayIntegers[i])
				switchX = true;
			if(y == e.arrayIntegers[i])
				switchY = true;
			if(switchX && switchY)
				break;
		}
	}
	else
	{
		e.arraySize = 0;
		e.arrayIntegers = new int[maxVertices];
	}
 
	if(!switchX && !switchY)
	{
		if(x < y)
		{
			e.arrayIntegers[e.arraySize] = x;
			e.arrayIntegers[e.arraySize+1] = y;
		}
		else
		{
			e.arrayIntegers[e.arraySize] = y;
			e.arrayIntegers[e.arraySize+1] = x;
		}
		switchX = switchY = true;
		e.arraySize += 2;
	}
 
	if(!switchX)
		e.arrayIntegers[e.arraySize++] = x;
	if(!switchY)
		e.arrayIntegers[e.arraySize++] = y;
}

 
#include <iostream>
const int maxEdges = 100;
 
 
 
/**********************************************
 *                 Edge                       *
 **********************************************
 * Edge is a structure that holds two vertices*
 * and the weight.                            *
 **********************************************/
struct Edge
{
       int vertOne;
       int vertTwo;
       int weight;
};
 
 
 
/**********************************************
 *                 Graph                      *
 **********************************************
 * Graph is a structure that holds the number *
 * of vertices, the number of edges, and a   *
 * pointer to the array of edges.            *
 **********************************************/
 
struct Graph
{
       int numVert;
       int numEdges;
       Edge * arrayEdges;
       ~Graph()
       {
               delete [] arrayEdges;
       }
};
 
 
 
 
void readGraph(Graph& g);
void printGraph(Graph& g);
void kruskalAlg(Graph& g);
int totalWeight(Graph& g);

#include <iostream>
#include <fstream>
#include "graph.h"
#include "equiv.h"
 
using namespace std;
 
 
 
/**********************************************
 *                 readGraph                  *
 **********************************************
 * readGraph reads in information about graph *
 * g from standard input then sets the edges  *
 * to the maximum number of edges avaliable.  *
 **********************************************/
void readGraph(Graph& g)
{
     int input;
     cin >> g.numVert;
     bool finished;
     finished = false;
	 if(g.numEdges > 0)
       delete [] g.arrayEdges;
     g.arrayEdges = new Edge[maxEdges];
     int k = 0;
	 while(!finished)
     {
                cin >> input;
                if(input==0) break;
                g.arrayEdges[k].vertOne = input;
                cin >> g.arrayEdges[k].vertTwo;
                cin >> g.arrayEdges[k].weight;
                k++;
     }
	 g.numEdges = k;
}
 
 
/************************************************
 *                 printGraph                   *
 ************************************************
 * printGraph prints out each vertice and weight*
 * of graph g from the standard input.          *
 **********************************************/
 
void printGraph(Graph& g)
{
     cout << "Vertices Weight" << endl;
     for(int k=0; k < g.numEdges; k++)
       cout << g.arrayEdges[k].vertOne << "  " << g.arrayEdges[k].vertTwo<< "\t  " << g.arrayEdges[k].weight << endl;
}
 
 
/**********************************************
 *                 kruskalAlg                 *
 **********************************************
 * kruskalAlg computes the minimal spanning   *
 * tree using Kruskal's algorithm, it takes   *
 * graph g as a parameter and yields it to    * 
 * graph k.                                   *
 **********************************************/
 
void kruskalAlg(Graph& g)
{
    Graph k;
	Equiv e;
	k.numVert = g.numVert;
	k.numEdges = 0;
	k.arrayEdges = new Edge[maxEdges];
	e.arraySize = 0;
	e.arrayIntegers = 0;
	int a = g.numEdges-1;
	while(a > 1)
	{
		for(int i = 0; i < a; i++)
		{
			if(g.arrayEdges[i].weight > g.arrayEdges[i+1].weight)
			{
				Edge edgeOne = g.arrayEdges[i+1];
				g.arrayEdges[i+1] = g.arrayEdges[i];
				g.arrayEdges[i] = edgeOne;
			}
		}
		a--;
	}
 
	for(int i = 0; i < g.numEdges; i++)
	{
		if(!together(e, g.arrayEdges[i].vertOne, g.arrayEdges[i].vertTwo))
		{
			combine(e, g.arrayEdges[i].vertOne, g.arrayEdges[i].vertTwo);
			k.arrayEdges[k.numEdges++] = g.arrayEdges[i];
		}
	}
	g.numEdges = k.numEdges;
	delete [] g.arrayEdges;
	g.arrayEdges = new Edge[maxEdges];
	for(int i = 0; i < k.numEdges; i++)
		g.arrayEdges[i] = k.arrayEdges[i];
}
 
 
/**********************************************
 *                 totalWeight                *
 **********************************************
 * totalWeight computes the total weight of   *
 * graph g.                                   *
 **********************************************/
 
 int totalWeight(Graph& g)
{
	 int total = 0;
	for(int k = 0; k < g.numEdges; k++)
		total += g.arrayEdges[k].weight;
	return total;
}

#include <cstdlib>
#include <iostream>
#include "graph.h"
 
using namespace std;
 
int main()
{
    Graph g;
    readGraph(g);
	cout << endl << "The input graph has " << g.numVert << " vertices, and its edges are as follows:" << endl << endl;
    printGraph(g);
	kruskalAlg(g);
	cout << endl << "A minimal spanning tree uses the following edges." << endl << endl;
	printGraph(g);
	cout << endl << "The total weight of the spanning tree is " << totalWeight(g) << endl << endl;
}