From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 graph/euler.cpp | 54 ++++++++++++++++++++----------------------------------
 1 file changed, 20 insertions(+), 34 deletions(-)

(limited to 'graph/euler.cpp')

diff --git a/graph/euler.cpp b/graph/euler.cpp
index a35ce13..0907ab2 100644
--- a/graph/euler.cpp
+++ b/graph/euler.cpp
@@ -1,40 +1,26 @@
-// Laufzeit: O(|V|+|E|)
-vector< vector<int> > adjlist, otherIdx;
-vector<int> cycle, validIdx;
+vector<vector<int>> idx;
+vector<int> to, validIdx, cycle;
+vector<bool> used;
 
-// Vertauscht Kanten mit Indizes a und b von Knoten n.
-void swapEdges(int n, int a, int b) {
-	int neighA = adjlist[n][a], neighB = adjlist[n][b];
-	int idxNeighA = otherIdx[n][a], idxNeighB = otherIdx[n][b];
-	swap(adjlist[n][a], adjlist[n][b]);
-	swap(otherIdx[n][a], otherIdx[n][b]);
-	otherIdx[neighA][idxNeighA] = b;
-	otherIdx[neighB][idxNeighB] = a;
-}
-
-// Entfernt Kante i von Knoten n (und die zugehörige Rückwärtskante).
-void removeEdge(int n, int i) {
-	int other = adjlist[n][i];
-	if (other == n) { //Schlingen.
-		validIdx[n]++;
-		return;
-	}
-	int otherIndex = otherIdx[n][i];
-	validIdx[n]++;
-	if (otherIndex != validIdx[other]) {
-		swapEdges(other, otherIndex, validIdx[other]);
-	}
-	validIdx[other]++;
+void addEdge(int a, int b) {
+	idx[a].push_back(sz(to));
+	to.push_back(b);
+	used.push_back(false);
+	idx[b].push_back(sz(to)); //für ungerichtet
+	to.push_back(a);
+	used.push_back(false);
 }
 
 // Findet Eulerzyklus an Knoten n startend.
-// Teste vorher, dass Graph zusammenhängend ist! Isolierten Knoten?
-// Teste vorher, ob Eulerzyklus überhaupt existiert!
+// init idx und validIdx
 void euler(int n) {
-	while (validIdx[n] < (int)adjlist[n].size()) {
-		int nn = adjlist[n][validIdx[n]];
-		removeEdge(n, validIdx[n]);
-		euler(nn);
-	}
-	cycle.push_back(n); // Zyklus in cycle in umgekehrter Reihenfolge.
+	for (;validIdx[n] < sz(idx[n]); validIdx[n]++) {
+		if (!used[idx[n][validIdx[n]]]) {
+			int nn = to[idx[n][validIdx[n]]];
+			used[idx[n][validIdx[n]]] = true;
+			used[idx[n][validIdx[n]] ^ 1] = true; //für ungerichtet
+			euler(nn);
+	}}
+	// Zyklus in cycle in umgekehrter Reihenfolge.
+	cycle.push_back(n);
 }
-- 
cgit v1.2.3