USTC机试之——最小生成树问题（文件中读取顶点信息并将最小生成树输出到另一文件中）

//图的最小生成树问题
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100
int Tree[N];
struct Edge{
     int a;
	 int b;
	 int cost;
	 bool operator < (const Edge &E)const{//重载小于符号
	     return cost<E.cost;
	 }
}E[N];
int findRoot(int x){//并查集思想寻找一顶点为x的根节点
    if(Tree[x]==-1)return x;
	else{
	   int temp=findRoot(Tree[x]);
	   Tree[x]=temp;
	   return temp;
	}

}
int main(){
    FILE *fp1,*fp2;
	int n,v;//分别代表顶点数和路径数
	int ans=0;//记录最小生成树的路径长度
	fp1=fopen("7.in","r");
	fp2=fopen("7.out","w");
	fscanf(fp1,"%d%d",&v,&n);
	for(int i=0;i<n;i++){
	   fscanf(fp1,"%d%d%d",&E[i].a,&E[i].b,&E[i].cost);//读入顶点及权值信息
	}
	for(i=0;i<v;i++){
	   Tree[i]=-1;
	}
	sort(E,E+n);//按照权值递增重新排序，此步是关键
	int a,b;
	for(int j=0;j<n;j++){//只要发现并查集中最小权值所在边不在同一个集合中即可合并并查集
	    a=findRoot(E[j].a);
        b=findRoot(E[j].b);
		if(a!=b){
		   Tree[a]=b;//合并并查集
           ans+=E[j].cost;//路径长度叠加
		   fprintf(fp2,"%d %d %d\n",E[j].a,E[j].b,E[j].cost);//同时将路径输出到该文件中
		}
	}
	fprintf(fp2,"最小生成树权值总和:%d",ans);
return 0;
}