【図論】POJ 1679-The Unique MST

タイトル:
連通の権限がなくて図の最小生成木が唯一であるかどうかを求めます.一意であれば、最小生成ツリーの重み値を出力します.一意でない場合は「Not Unique!」を出力します.
考え方:
最小生成木と次小生成木を求め,重み値が等しいか否かを判断し,等しいと一意ではない.
最小生成ツリーはPrimアルゴリズムで求められ,重み値をw(MST)とする.二次小生成木の求め方については、最小生成木を求めた後、MSTにない各辺eを列挙し、eの起点をu、終点をv、重み値をcとすると、他方の生成木Tiの重み値はw(MST)+c-M(u,v)であり、M(u,v)はMSTにおけるu~vの最大重み値辺の重み値であり、Primアルゴリズムで同時に求めることができる.最後にすべてのTiの最小値をとると,二次生成ツリーの重み値となる.
コード:

#include 
#include 
#include 
#include 
using namespace std;

int N, M;
int G[105][105];
bool T[105][105];
int LEN[105][105];

struct Edge {
	int u, v, w;
	Edge(): u(-1), v(-1), w(0) {
	}
	Edge(int u, int v, int w): u(u), v(v), w(w) {
	}
};

struct Edge_Greater {
	bool operator () (const Edge lhs, const Edge rhs) const {
		return lhs.w > rhs.w;
	}
};

priority_queue, Edge_Greater> Queue;
int FL[105];

int Kruskal() {
	for (int i=1; i<=N; i++) {
		FL[i] = i;
	}
	memset(LEN, 0, sizeof(LEN));
	memset(T, 0, sizeof(T));
	int ans = 0;
	int cnt = 0;
	while (!Queue.empty() && cnt < N-1) {
		Edge e = Queue.top(); Queue.pop();
		int u = e.u; int v = e.v; int w = e.w; 
		if (FL[u] == FL[v]) {
			continue;
		}
		ans += w;
		T[u][v] = T[v][u] = true;
		int flu = FL[u]; int flv = FL[v];
		for (int i=1; i<=N; i++) {
			if (FL[i] == flu) {
				for (int j=1; j<=N; j++) {
					if (FL[j] == flv) {
						LEN[i][j] = LEN[j][i] = w;
					}
				} 
			}
		}
		for (int i=1; i<=N; i++) {
			if (FL[i] == flv) {
				FL[i] = flu;
			}
		}
	}
	return ans;
}

int main() {
	int K;
	scanf("%d", &K);
	while (K--) {
		scanf("%d%d", &N, &M);
		memset(G, 0x3F, sizeof(G));
		while (!Queue.empty())
			Queue.pop();
		for (int i=0; i

心得:
次小生成木の求め方を学んだ.