#include
#include
#include
#include
using?namespace?std;
//去邊法構造最小生成樹
?
typedef?struct?graph{
	int?vertexnumedgenum;
	int?matrix[100][100];		//坑上存weight?
}graph;
typedef?struct?edge{
	int?weigh;
	int?pver1pver2;
	int?flag;		//flag=1被找過，flag=2沒被找過?
}edge;

int?Findmaxwei（edge*?graph&）;
void?Maketree（graph&int*）;
int??IfOKtoRemove（int??edge?*graph?&?）;?

int?main（）
{
	int?ik;
	graph?G;
	printf（“輸入圖的頂點數：“）;?
	scanf（“%d“&G.vertexnum）;
	printf（“輸入邊數：“）;?
	scanf（“%d“&G.edgenum）;
	printf（“輸入鄰接矩陣：\n“）;
	
	int?vert[G.vertexnum];
	for（i=0;i		for（k=0;k			scanf（“%d“&G.matrix[i][k]）;
	for（i=0;i		vert[i]=i;		//數組每個坑代表一個vertex，坑里的值為點的等價類號		
	Maketree（Gvert）;
	
	return?0;	
}

void?Maketree（graph?&Gint*?vert）
{
	int?ikj=0en=G.edgenummednum=G.edgenum;		//en=?num?of?edges?remained?
	edge?Edge[G.edgenum];
	
	for（i=0;i		for（k=i;k		{
			if（G.matrix[i][k]!=0）
			{
				Edge[j].flag=2;
				Edge[j].pver1=i;
				Edge[j].pver2=k;
				Edge[j].weigh=G.matrix[i][k];
				j++;
			}
		}		//j=?edgenum
			
	while（en>G.vertexnum-1）
	{?	
		k=Findmaxwei（Edge?G）;		//k=newver的最小權邊在?Edge里的下標?
		if（k==-1）	break;
		
		Edge[k].flag