Source code for submission s908

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;
}
 

Diff to submission s811

--- 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;