#include <stdio.h>
#include <conio.h>
#include <iostream.h>

int kruskal_mst(int set[],struct krus edge[],int n,int m);


struct krus{
		 int v1;
		 int v2;
		 int weight;
};
int g=0;

//***********************************************
void sort(struct krus ed[],int m)
{
 struct krus temp;
 for (int i=0;i<m;i++)
  for (int j=i+1;j<m;j++)
	if (ed[j].weight<ed[i].weight)
	 {
	  temp=ed[i];
	  ed[i]=ed[j];
	  ed[j]=temp;
	  }
}

//***********************************************
int kruskal_mst(int set[],struct krus edge[],int n,int m)
{
 int fe=0;
 int p=0;
 struct krus e;
 while (fe<n-1 && g<m)
 {
  e=edge[g++];
  if (set[e.v1] != set[e.v2])
  {
	p+=e.weight;
	int k=set[e.v1];
	for (int i=0;i<n;i++)
	  if (set[i]==k)
	 set[i]=set[e.v2];
	fe++;
	}
  }
 if(fe==n-1) return p;
 else
	return -1;
}
//***********************************************
int perim(int set[],struct krus edge[],int n,int m)
{
 int fe=0;
 int p=0;
 struct krus e;
 while (fe<n-1)
 {
  //********************************
  int y=0;
  e.weight=0;
  for (int i=0;i<m;i++)
	 if ((set[edge[i].v1]==0 && set[edge[i].v2]!=0) || (set[edge[i].v2]==0 && set[edge[i].v1]!=0))
		 {
	 if(y==0)
		{
		  e=edge[i];
		  y++;
		 }
	 else
		 if (e.weight>edge[i].weight)
		e=edge[i];
		 }
	//**********************************
  if (y!=0)
  {
	p+=e.weight;
	cout<<"("<<e.v1<<","<<e.v2<<") => W :"<<e.weight<<"\t";
	set[e.v1]=0;
	set[e.v2]=0;
	fe++;
  }
	else
		break;
  }
  return p;

}

//***********************************************
int menu();
//***********************************************
void main()
{

  int n,m;

  while (1)
	 {
    cout<<"Input Num Vertex : ";
		 cin>>n;
		 int set[10];
		 for (int i=0;i<n;i++)
		 set[i]=i;
		 cout<<"Input Num Yal : ";
		 cin>>m;
		 struct krus edge[20];
		 for (i=0;i<m;i++)
		 {
		 cout<<" Num V1 : ";  cin>>edge[i].v1;
		 cout<<" Num V2 : ";  cin>>edge[i].v2;
		 cout<<" Weight : ";  cin>>edge[i].weight;
  }

		 clrscr() ;
		 switch (menu())
		 {

		case 1:

		sort(edge,m);

		for (i=0;i<m;i++)
		cout<<"("<<edge[i].v1<<","<<edge[i].v2<<") => W :"<<edge[i].weight<<"\n";
		cout<<"Weight Is : "<<kruskal_mst(set,edge,n,m);

		break ;

		case 2:

		gotoxy(wherex()+30,wherey()-2);
		cout<<"("<<edge[i].v1<<","<<edge[i].v2<<") => W :"<<edge[i].weight<<"\n";
		gotoxy(1,wherey()+2);

		cout<<"\nWeight Is : "<<perim(set,edge,n,m);

	  }//end of switch
	} //end of while
} // end of main
//********************
int menu()
{
	int c;
	cout << "1.Enter number to Kruskal\n";
	cout << "2.Enter number to Prime\n";
	cout << "3.......\n";
	cout << "4.Exit from program\n";
	cout << "Enter your select(1-4):";
	cin >> c;
	return c;
}