1. Kruskal(并查集模板)：
/*
Kruskal：并查集实现，记录两点和距离，按距离升序排序，O (ElogE)
*/
struct Edge {
int u, v, w;
bool operator < (const Edge &r) const {
return w < r.w;
}
}edge[E];
sort (edge+1, edge+1+m);
if (!uf.same (x, y)) uf.Union (x, y), ans += w;
2. Prim：
O (n ^ 2)：
/*
Prim：Dijkstra思想，邻接矩阵实现，适合稠密图, O (n ^ 2)
不连通返回-1，或返回最小生成树长度(MST)
*/
int Prim(int s) {
memset (vis, false, sizeof (vis));
memset (d, INF, sizeof (d)); d[s] = 0;
int ret = 0;
for (int i=1; i<=n; ++i) {
int mn = INF, u = -1;
for (int i=1; i<=n; ++i) {
if (!vis[i] && d[i] < mn) mn = d[u=i];
}
if (u == -1) return -1;
vis[u] = true; ret += d[u];
for (int i=1; i<=n; ++i) {
if (!vis[i] && d[i] > w[u][i]) {
d[i] = w[u][i];
}
}
}
return ret;
}
O (ElogV)：
/*
Prim：Dijkstra思想，优先队列优化，适合稀疏图，O (ElogV)
不连通返回-1，或返回最小生成树长度(MST)
*/
int Prim(int s) {
memset (vis, false, sizeof (vis));
memset (d, INF, sizeof (d));
priority_queue<Edge> Q;
for (int i=head[s]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (d[v] > w) {
d[v] = w; Q.push (Edge (v, d[v]));
}
}
vis[s] = true; d[s] = 0; int ret = 0;
while (!Q.empty ()) {
int u = Q.top ().v; Q.pop ();
if (vis[u]) continue;
vis[u] = true; ret += d[u];
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (!vis[v] && d[v] > w) {
d[v] = w; Q.push (Edge (v, d[v]));
}
}
}
return ret;
}