#include <iostream>
using namespace std;
int M,N; //顶点数和边数
int *a; //动态分配顶点个数大小的数组，存储相应的父结点
struct Edge{
int v;
int w; //存储边，V，W对应两个端点
int weight; //存储边的权重
};
Edge *edge; //动态分配边的条数的大小的数组，存储边
void Init()
{
cout << "输入顶点数和边数:" << endl;
cin >> M >> N;
while(M < 2 || N < 1)
{
cout << "重新输入顶点数和边数:" << endl;
cin >> M >> N;
}
a = new int[M];
edge = new Edge[N];
cout << "输入" << N << "条边对应的两个端点及权值（值之间以空格分开，顶点号在0与" << M-1 << "之间）：" << endl;
for(int i = 0;i < N;i++)
{
int u,v,w;
cin >> u >> v >> w;
while(u < 0 || u > M-1 || v < 0 || v > M-1 || w <= 0)
{
cout << "数据出错，请重新输入此边数据:" << endl;
cin >> u >> v >> w;
}
edge[i].v = u,edge[i].w = v;
edge[i].weight = w;
} //为edge数组赋值
//初始化a数组
for(int i = 0; i < M;i++)
a[i] = -1;
}
int father(int m)
{
for(;a[m] != -1;)
m = a[m];
return m;
}
bool Union(int m,int n)
{
m = father(m);
n = father(n);
if( m == n )
return 0;
else{
a[n] = m;
return 1;
}
}
int partition(int low,int high)
{
Edge *tmp = new Edge;
tmp->v = edge[low].v;
tmp->w = edge[low].w;
tmp->weight = edge[low].weight;
while(low < high)
{
while(low < high && tmp->weight <= edge[high].weight) --high;
edge[low].v = edge[high].v;
edge[low].w = edge[high].w;
edge[low].weight = edge[high].weight;
while(low < high && edge[low].weight <= tmp->weight) ++low;
edge[high].v = edge[low].v;
edge[high].w = edge[low].w;
edge[high].weight = edge[low].weight;
}
edge[low].v = tmp->v;
edge[low].w = tmp->w;
edge[low].weight = tmp->weight;
delete tmp;
return low;
}
void Qsort(int low,int high)
{
if(low < high)
{
int interr = partition(low,high);
Qsort(low,interr-1);
Qsort(interr+1,high);
}
}
int * mst()
{
Init();
int *a = new int[M-1];
int count = 0;
Qsort(0,N-1);
for(int i = 0;i < N;i++)
{
if(Union(edge[i].v,edge[i].w))
a[count++] = i;
if(count == M-1) break;
}
return a;
}
int main()
{
int *b = mst();
cout << "最小生成树如下:" << endl;
for(int i = 0;i < M-1;i++)
{
int m = b[i];
cout << edge[m].v << ' ' << edge[m].w << ' ' << edge[m].weight << endl;
}
delete b;
return 0;
}
