UVa 1208 - Oreon

// UVa 1208 - Oreon
// Minimum Spanning Tree

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

struct edge {
	int a, b, c;
	edge(int x, int y, int z) {
		a = x;
		b = y;
		c = z;
	}
};

bool operator <(const edge & x, const edge & y) {
	return x.c < y.c || (x.c == y.c && x.a < y.a)
			|| (x.c == y.c && x.a == y.a && x.b < y.b);
}

int input[26][26], parent[26], rank[26];

void MakeSet(int x) {
	parent[x] = x;
	rank[x] = 0;
}

int Find(int x) {
	if (parent[x] != x)
		parent[x] = Find(parent[x]);
	return parent[x];
}

void Union(int x, int y) {
	int xRoot = Find(x);
	int yRoot = Find(y);
	if (xRoot == yRoot)
		return;
	if (rank[xRoot] < rank[yRoot])
		parent[xRoot] = yRoot;
	else if (rank[xRoot] > rank[yRoot])
		parent[yRoot] = xRoot;
	else {
		parent[yRoot] = xRoot;
		rank[xRoot] = rank[xRoot] + 1;
	}
}

int main() {
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++) {
		int n;
		vector<edge> edges;

		// input
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				char dummy;
				scanf("%d%c", &input[i][j], &dummy);
				if (i < j && input[i][j] != 0)
					edges.push_back(edge(i, j, input[i][j]));
			}
			MakeSet(i);
		}

		vector<edge> mst;
		// Kruskal's
		sort(edges.begin(), edges.end());
		for (vector<edge>::const_iterator I = edges.begin(); I != edges.end();
				I++) {
			int aRoot = Find(I->a);
			int bRoot = Find(I->b);
			if (aRoot != bRoot) {
				mst.push_back(*I);
				if (mst.size() == n)
					break;
				Union(I->a, I->b);
			}
		}

		printf("Case %d:\n", t);
		for (vector<edge>::const_iterator I = mst.begin(); I != mst.end(); I++)
			printf("%c-%c %d\n", I->a + 'A', I->b + 'A', I->c);

	}
	return 0;
}