From e8356c886f8431adf2ebeede299896947372e4b4 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Tue, 28 Jan 2025 15:12:53 +0100
Subject: shorter euler tour

---
 content/graph/euler.cpp | 29 ++++++++++++-----------------
 1 file changed, 12 insertions(+), 17 deletions(-)

(limited to 'content/graph/euler.cpp')

diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp
index a5ea192..fff9371 100644
--- a/content/graph/euler.cpp
+++ b/content/graph/euler.cpp
@@ -1,23 +1,18 @@
-vector<vector<int>> idx;
-vector<int> to, validIdx, cycle;
-vector<bool> used;
+vector<vector<pair<int, int>>> adj;
+vector<int> cycle;
 
 void addEdge(int u, int v) {
-	idx[u].push_back(sz(to));
-	to.push_back(v);
-	used.push_back(false);
-	idx[v].push_back(sz(to)); // für ungerichtet
-	to.push_back(u);
-	used.push_back(false);
+	adj[u].emplace_back(v, sz(adj[v]));
+	adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for undirected
 }
 
-void euler(int v) { // init idx und validIdx
-	for (;validIdx[v] < sz(idx[v]); validIdx[v]++) {
-		if (!used[idx[v][validIdx[v]]]) {
-			int u = to[idx[v][validIdx[v]]];
-			used[idx[v][validIdx[v]]] = true;
-			used[idx[v][validIdx[v]] ^ 1] = true; // für ungerichtet
-			euler(u);
-	}}
+void euler(int v) {
+	while (!adj[v].empty()) {
+		auto [u, rev] = adj[v].back();
+		adj[v].pop_back();
+		if (u == -1) continue;
+		adj[u][rev].first = -1; // remove for undirected
+		euler(u);
+	}
 	cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge.
 }
-- 
cgit v1.2.3