Kruskals.cpp

/******************************KRUSKALS ALGORITHM********************************/
#include<iostream>
#include<set>
#include<algorithm>
#include<queue>
#include<utility>
#include<exception>
#include<conio.h>

using namespace std;
void print_pair(pair<int,int> p){
	cout<<"\n("<<(char)(p.first+'A'-1)<<","<<(char)(p.second+'A'-1)<<")";
}
class edge{
	public:
	int u;
	int v;
	int w;
	bool operator<(const edge& e)const{
		return e.w<w;
	}
	edge(int a,int b,int c){u=a,v=b,w=c;}
};

int main(){
	int n,p,q,w;
	cout<<"Enter the number of nodes";
	cin>>n;
	set<int>* s=new set<int>[n];
	set<pair<int ,int> > A;
	for (int i=1;i<=n;i++){
		s[i-1].insert(i);
			} 
	try{
		cout<<"Enter the edges with its coresponding weights:";
		priority_queue<edge > UV;
		while(cin>>p){
		if(!p)break;
		cin>>q>>w;
		UV.push(edge(p,q,w));
	}
	while(!UV.empty()){
		int i,j;
		edge tmp=UV.top();
		UV.pop();
		for(i=0;i<n&&s[i].find(tmp.u)==s[i].end();i++);
		for(j=0;j<n&&s[j].find(tmp.v)==s[j].end();j++);
		if(i!=j){
			A.insert(make_pair(tmp.u,tmp.v));
			s[i].insert(s[j].begin(),s[j].end());
			s[j].clear();
			}      
			 }
		for_each(A.begin(),A.end(),print_pair);
	}
	catch(exception& e){cout<<"\nException"<<e.what();}
	if(s)
		delete[] s;
	getch();
}