Merge branch 'eulerian-path'

tonowak · Mar 20, 2024 · d79e377 · d79e377
2 parents 269026f 9381c8e
commit d79e377
Show file tree

Hide file tree

Showing 2 changed files with 20 additions and 27 deletions.
diff --git a/code/graph/eulerian-path/main.cpp b/code/graph/eulerian-path/main.cpp
@@ -1,15  1,11 @@
 /*
- * Opis: O(n   m), ścieżka eulera.
  * Opis: O(n   m), ścieżka eulera. Zwraca tupla (exists, ids, vertices).
  * W \texttt{exists} jest informacja czy jest ścieżka/cykl eulera,
  * \texttt{ids} zawiera id kolejnych krawędzi,
  * \texttt{vertices} zawiera listę wierzchołków na tej ścieżce.
  * Dla cyklu, \texttt{vertices[0] == vertices[m]}.
  */
-struct EulerRet {
-	bool exists = false;
-	vector<int> ids, vertices;
-};
-EulerRet eulerian_path(int n, const vector<pair<int, int>> &edges, bool directed) {
 tuple<bool, vector<int>, vector<int>> eulerian_path(int n, const vector<pair<int, int>> &edges, bool directed) {
 	vector<int> in(n);
 	vector<vector<int>> adj(n);
 	int start = 0;
@@ -24,6  20,8 @@ EulerRet eulerian_path(int n, const vector<pair<int, int>> &edges, bool directed
 	int cnt_in = 0, cnt_out = 0;
 	REP(i, n) {
 		if (directed) {
 			if (abs(ssize(adj[i]) - in[i]) > 1)
 				return {};
 			if (in[i] < ssize(adj[i]))
 				start = i,   cnt_in;
 			else
@@ -32,11  30,7 @@ EulerRet eulerian_path(int n, const vector<pair<int, int>> &edges, bool directed
 		else if (ssize(adj[i]) % 2)
 			start = i,   cnt_in;
 	}
-	if (directed)
-		REP(i, n)
-			if (abs(ssize(adj[i]) - in[i]) > 1)
-				return EulerRet();
-	EulerRet ret;
 	vector<int> ids, vertices;
 	vector<bool> used(ssize(edges));
 	function<void (int)> dfs = [&](int v) {
 		while (ssize(adj[v])) {
@@ -45,17  39,16 @@ EulerRet eulerian_path(int n, const vector<pair<int, int>> &edges, bool directed
 			if (used[id]) continue;
 			used[id] = true;
 			dfs(u);
-			ret.ids.emplace_back(id);
 			ids.emplace_back(id);
 		}
 	};
 	dfs(start);
 	if (cnt_in   cnt_out > 2 or not all_of(used.begin(), used.end(), identity{}))
-		return EulerRet();
-	reverse(ret.ids.begin(), ret.ids.end());
-	if (ssize(ret.ids))
-		ret.vertices = {start};
-	for (int id : ret.ids)
-		ret.vertices.emplace_back(ret.vertices.back() ^ edges[id].first ^ edges[id].second);
-	ret.exists = true;
-	return ret;
 		return {};
 	reverse(ids.begin(), ids.end());
 	if (ssize(ids))
 		vertices = {start};
 	for (int id : ids)
 		vertices.emplace_back(vertices.back() ^ edges[id].first ^ edges[id].second);
 	return {true, ids, vertices};
 }
diff --git a/code/graph/eulerian-path/test.cpp b/code/graph/eulerian-path/test.cpp
@@ -11,7  11,7 @@ void test() {
 		edges.emplace_back(rd(0, n - 1), rd(0, n - 1));
 	debug(n, m, directed, edges);
 
-	EulerRet ep = eulerian_path(n, edges, directed);
 	auto [ep_exists, ep_ids, ep_vertices] = eulerian_path(n, edges, directed);
 
 	bool exists = m ? false : true;
 	REP(start, n) {
@@ -38,12  38,12 @@ void test() {
 		if (exists)
 			break;
 	}
-	debug(exists, ep.exists);
-	assert(exists == ep.exists);
 	debug(exists, ep_exists);
 	assert(exists == ep_exists);
 
 	if (exists) {
-		int v = ep.vertices.empty() ? 0 : ep.vertices.front();
-		const auto ids = ep.ids;
 		int v = ep_vertices.empty() ? 0 : ep_vertices.front();
 		const auto ids = ep_ids;
 		assert(v >= 0 and v < n);
 		assert(ssize(ids) == m);
 		for (int id : ids)
@@ -61,8  61,8 @@ void test() {
 				v ^= a ^ b;
 			}
 		}
-		const auto vertices = ep.vertices;
-		assert((m == 0 and ep.vertices.empty()) or (m > 0 and ssize(vertices) == m   1));
 		const auto vertices = ep_vertices;
 		assert((m == 0 and ep_vertices.empty()) or (m > 0 and ssize(vertices) == m   1));
 		for (int x : vertices)
 			assert(x >= 0 and x < n);
 		REP(i, m) {