[정올 1060] 최소비용신장트리

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=340&sca=99 

JUNGOL

#include <stdio.h>

const int MAX = 100100;
//G는 idx인 점이 어느 곳과 연결되어 있는지를 알려줌
int N, G[10100], M[103][103]; 
int ans;

int Find(int r) { //자기가 Root면 자기 리턴, 아니면 찾아감
	return G[r] = r == G[r] ? r : Find(G[r]);
}

int main() {
	int cnt, mini, minj, min = MAX, startGp;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		G[i] = i; //어느 그룹에 속해있는지
		for (int j = 1; j <= N; j++) { 
			scanf("%d", &M[i][j]); 
			if (M[i][j] && M[i][j] < min) {
				min = M[i][j];
				startGp = i;
			}
		}
	}
	cnt = N - 1;
	while (cnt--) {
		min = MAX;
		mini = minj = 0;
		for (int i = 1; i <= N; i++) { //
			if (Find(i) != startGp) continue; 
			//같은 그룹인 놈들 중
			for (int j = 1; j <= N; j++) {
				//다른 그룹과 연결된 놈들 중 가장 짧은 것 선택
				if (Find(j) == startGp) continue; 
				if (M[i][j] < min) { mini = i, minj = j; min = M[mini][minj]; }
			}
		}
		ans += M[mini][minj]; //ans에 업데이트
		G[minj] = startGp; //두 점을 한 그룹으로 합침
	}
	printf("%d\n", ans);

	return 0;
}