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')

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


From 0c55282e01f07dd6bad486b591b156f7e9aa8fa7 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Tue, 28 Jan 2025 15:16:03 +0100
Subject: fix pdf line break

---
 content/graph/euler.cpp |   2 +-
 tcr.pdf                 | Bin 695526 -> 703218 bytes
 2 files changed, 1 insertion(+), 1 deletion(-)

(limited to 'content/graph')

diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp
index fff9371..f375d42 100644
--- a/content/graph/euler.cpp
+++ b/content/graph/euler.cpp
@@ -3,7 +3,7 @@ vector<int> cycle;
 
 void addEdge(int u, int v) {
 	adj[u].emplace_back(v, sz(adj[v]));
-	adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for undirected
+	adj[v].emplace_back(u, sz(adj[u])-1); // remove for undirected
 }
 
 void euler(int v) {
diff --git a/tcr.pdf b/tcr.pdf
index 157dbc4..2aa3284 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3


From 9682f525a3f4c07de062f940233cec734543e8a7 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Tue, 28 Jan 2025 15:32:21 +0100
Subject: fix comments

---
 content/graph/euler.cpp | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp
index f375d42..0b39f53 100644
--- a/content/graph/euler.cpp
+++ b/content/graph/euler.cpp
@@ -3,15 +3,15 @@ vector<int> cycle;
 
 void addEdge(int u, int v) {
 	adj[u].emplace_back(v, sz(adj[v]));
-	adj[v].emplace_back(u, sz(adj[u])-1); // remove for undirected
+	adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for directed
 }
 
 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
+		if (u == -1) continue; // remove for directed
+		adj[u][rev].first = -1; // remove for directed
 		euler(u);
 	}
 	cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge.
-- 
cgit v1.2.3


From 939e434ae205af10cccb4ce8e4103e9ec3f1e7a1 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Wed, 12 Feb 2025 11:11:10 +0100
Subject: added comment

---
 content/graph/euler.cpp |   4 ++--
 tcr.pdf                 | Bin 703218 -> 699076 bytes
 2 files changed, 2 insertions(+), 2 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp
index 0b39f53..e81cebe 100644
--- a/content/graph/euler.cpp
+++ b/content/graph/euler.cpp
@@ -1,4 +1,4 @@
-vector<vector<pair<int, int>>> adj;
+vector<vector<pair<int, int>>> adj; // gets destroyed!
 vector<int> cycle;
 
 void addEdge(int u, int v) {
@@ -10,7 +10,7 @@ void euler(int v) {
 	while (!adj[v].empty()) {
 		auto [u, rev] = adj[v].back();
 		adj[v].pop_back();
-		if (u == -1) continue; // remove for directed
+		if (u < 0) continue; // remove for directed
 		adj[u][rev].first = -1; // remove for directed
 		euler(u);
 	}
diff --git a/tcr.pdf b/tcr.pdf
index 2aa3284..34cf09c 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3