ALDS1_12_A Minimum Spanning Tree

問題
最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge

最小全域木を求める問題です。クラスカルのアルゴリズムで実装してみました。
下記の東北大のレジュメが分かり易かったです。

参考
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/ad09-10.pdf

アルゴリズムの大まかな流れは
１．閉路ができないように、コストの小さい辺から選ぶ
２．全ての頂点が選ばれるまで、１を繰り返す
というものです。コストの小さい辺から選ぶということで、辺の情報（コスト、端点のid）を構造体にまとめ、それをqsortでソートしました。
qsortの使い方はこちらが分かり易かったです。なんでもソートできちゃうんですね。
qsort で構造体配列をソートする例 | C言語のサンプル | C入門 基本情報対策講座のcClip

「閉路ができないように」というのは、Union-Findを利用しました。
「閉路ができない」⇔「二頂点が同じグループじゃない」てな感じです。

#include<stdio.h>
#include<stdlib.h>
#define N 100
#define LARGE 10000

typedef struct edge{
	int cost;
	int u;
	int v;
}edge;

/*qsort用*/
int cmp(const void *p,const void *q){
	return ((edge*)p)->cost - ((edge*)q)->cost;
}


int find(int u,int par[]){
	if(par[u]==u){
		return u;
	}else {
		return par[u]=find(par[u],par);
	}
}

void merge(int u,int v,int par[]){
	if(par[u] < par[v]){
		if(v!=par[v])
			merge(u,par[par[v]],par);
		par[v]=par[u];
	}
	else {
		if(u!=par[u])
			merge(v,par[par[u]],par);
		par[u]=par[v];
	}
	return;
}



int main(){
	int i,j,n;
	int num=0;/*edgeの個数*/
	int ans=0;
	int a[N][N];
	edge E[LARGE];/*edge*/
	int par[N];/*親の配列*/
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++)par[i]=i;
	
	
	/*隣接行列の読み込み*/
	for(i=0;i<n;i++){
	
		for(j=0;j<n;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]!=-1 && j>=i+1){
				E[num].cost=a[i][j];
				E[num].u=i;
				E[num++].v=j;
			}
		}
		
	}
	
	/*edgeのソート*/
	qsort(E,num,sizeof(edge),cmp);
	
	for(i=0;i<num;i++){
		if(find(E[i].u,par) != find(E[i].v,par)){
			merge(E[i].u,E[i].v,par);
			ans+=E[i].cost;
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
	
}

学ぶことが多く、勉強不足を痛感しました。