Go to diff to previous submission
#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)); } int connect(int u, int v) { int uroot = find_set(u); int vroot = find_set(v); UF[uroot] = UF[vroot]; CS[uroot] = CS[vroot] = CS[uroot] + CS[vroot]; return CS[uroot]; } 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)) { if (connect(e.u, e.v) == N) all = true; netl += e.l; } ++ei; } if (all) cout << netl << '\n'; else cout << "disconnected\n"; } return 0; }
--- c4.s811.cteam012.spider.cpp.0.spider.cpp +++ c4.s908.cteam012.spider.cpp.0.spider.cpp @@ -22,8 +22,11 @@ return (find_set(u) == find_set(v)); } -void connect(int u, int v) +int connect(int u, int v) { - UF[u] = UF[v]; - CS[u] = CS[v] = CS[u] + CS[v]; + int uroot = find_set(u); + int vroot = find_set(v); + UF[uroot] = UF[vroot]; + CS[uroot] = CS[vroot] = CS[uroot] + CS[vroot]; + return CS[uroot]; } @@ -63,8 +66,7 @@ edge e = E[ei]; if (!connected(e.u, e.v)) { - connect(e.u, e.v); - netl += e.l; - if (CS[e.u] == N) + if (connect(e.u, e.v) == N) all = true; + netl += e.l; } ++ei;