spider.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
int u, v, l;
bool operator<(const edge & rhs) const
{ return l < rhs.l; }
};
vector<int> UF;
vector<int> CS;
int find_set(int n) {
if (n != UF[n])
UF[n] = find_set(UF[n]);
return UF[n];
}
bool connected(int u, int v)
{
return (find_set(u) == find_set(v));
}
void connect(int u, int v)
{
UF[u] = UF[v];
CS[u] = CS[v] = CS[u] + CS[v];
}
int main()
{
ios_base::sync_with_stdio(false);
int N, M;
while (cin >> N) {
cin >> M;
vector<edge> E (M);
UF = vector<int> (N+1);
CS = vector<int> (N+1);
long netl = 0;
// UF
for (int i = 0; i <= N; ++i) {
UF[i] = i;
CS[i] = 1;
}
// load and sort
for (int i = 0; i < M; ++i) {
edge e;
cin >> e.u >> e.v >> e.l;
E[i] = e;
}
sort (E.begin(), E.end());
// connect longest
edge longest = E.back();
netl -= longest.l;
connect(longest.u, longest.v);
E.pop_back(); --M;
bool all = false; int ei = 0;
while (ei < M && !all) {
edge e = E[ei];
if (!connected(e.u, e.v)) {
connect(e.u, e.v);
netl += e.l;
if (CS[e.u] == N)
all = true;
}
++ei;
}
if (all) cout << netl << '\n';
else cout << "disconnected\n";
}
return 0;
}