#include <iostream>
#include <iomanip>
using namespace std;
#define MAXNODE 100
#define MAXEDE 100
struct edge
{
int v1,v2;
int cost;
};
class MGraph
{
private:
int n,e; //定义无向图的顶点数和边数
int vexs[MAXNODE],i; //定义顶点信息
edge key[MAXEDE];
public:
MGraph(){
cout<<"Please input the numbers of dingdianshu and bianshu(like this dingdianshu,dianshu): ";//请输入顶点数和边数（输入格式为：顶点数，边数）
cin>>n>>e; //输入顶点数和边数
//cout<<"Please input the information of dingdian :";//请输入顶点信息（输入格式为：i）
//for(i=0;i<n;i++)
// cin>>vexs[i]; //输入顶点信息，建立顶点表
}
void CreateMGraph()
{
// 建立无向图G的邻接矩阵存储
// MGraph();
int i,j,k;
int bian[100][100];
int cst;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
bian[i][j]=0; //初始化邻接矩阵
cout<<"Please input the two dingdian and their cost(like this i,j,cst):";//请输人每条边对应的两个顶点及其权值（输入格式为:i,j,q）
for(k=1;k<=e;k++)
{
cout<<"Please input the dingdian i and j and its cost:";
cin>>i>>j>>cst; //输入e条边信息，建立邻接矩阵
bian[i][j]=cst;
bian[j][i]=cst;
key[k].cost=cst; //建立一个关键码数组 ，方便后面的堆排序
key[k].v1=i; //第k条边的第一个顶点为i
key[k].v2=j; //第k条边的第二个顶点为j
}
} //CreateMGraph
void HeapAdjust(int s,int t)
{
//edges[s...t]中的记录关键码除eedges[s]外均满足堆的特性，本算法将其进行筛选，使其成为大顶堆
int i,j;
edge rc;
rc=key[s];
i=s;
for(j=2*i;j<=t;j=2*j) //沿关键码较小的孩子结点向下筛选
{
if(j<t && key[j].cost<key[j+1].cost)
j=j+1; //j指向edges的关键码较小的孩子
if(rc.cost>key[j].cost)
break; //不用调到叶子就到位了
key[i]=key[j];
i=j; //准备继续向下调整
}
key[i]=rc; //插入
}
void Heapsort()
{
//大顶堆排序
int i;
edge tmp;
for(i=e/2;i>0;i--) //将edges[1]....edges[n]建成堆
HeapAdjust(i,e);
for(i=e;i>1;i--)
{
tmp=key[1]; //堆顶edges[1]与堆底edges[i]交换
key[1]=key[i];
key[i]=tmp;
HeapAdjust(1,i-1); //将edges[1]...edges[i-1]重新调整为堆
}
}
int Find(int father[MAXEDE], int v)
{
//寻找定点v所在树的根结点
int t;
t=v;
while(father[t]>=0)
t=father[t];
return(t);
}
void Kruskal()
{
//用Kruskal方法构造有n个顶点图edges的最小生成树
//edges[]中的数据已按cost值由小到大排序
int father[MAXEDE];
//对于n个顶点的网，设置1个数组father[n]，
//其初值为father[i]=-1(i=0,1...n-1),表示各个顶点在不同的连通分量上，然后依次取出edges数组中的每条边的 2 个顶点，查处他们所属的连通分量 ，若
//不属于同一个连通分量，则将这条边作为最小生成树的边输出，并合并他们所属的连通分量，
int i,j,vf1,vf2;
for(i=0;i<n;i++)
father[i]=-1;
i=1;
j=1;
while(i<MAXEDE && j<n)
{
vf1=Find(father,key[i].v1);
vf2=Find(father,key[i].v2);
if(vf1!=vf2)
{
father[vf2]=vf1;
j++;
cout<<key[i].v1<<key[i].v2<<endl;
}
i++;
}
}
};//MGraph
int main()
{
//1。然后按边上的权值进行堆排序 ，传入的是边信息
//2。然后将排好序的边传到 Kruskal中，进行最小生成树的构造
MGraph g;
g.CreateMGraph();
g.Heapsort();
g.Kruskal();
return 1;
}
