From f1b3e645381d9b8ea8197fb1473f115de2ee8f96 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc57.atis-stud.uni-karlsruhe.de>
Date: Sat, 22 Nov 2014 13:03:04 +0100
Subject: adding string chapter

---
 tcr.tex | 1 +
 1 file changed, 1 insertion(+)

(limited to 'tcr.tex')

diff --git a/tcr.tex b/tcr.tex
index 4dce95e..4328b73 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -56,6 +56,7 @@
 \input{graph/graph}
 \input{geometry/geometry}
 \input{math/math}
+\input{string/string}
 \input{sonstiges/sonstiges}
 
 \end{document}
\ No newline at end of file
-- 
cgit v1.2.3


From 0bdabf851fd4a83e57fced5864aa85af7029ad48 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc57.atis-stud.uni-karlsruhe.de>
Date: Sat, 22 Nov 2014 16:59:45 +0100
Subject: Dokument gebaut

---
 graph/graph.tex |   7 +++++++
 tcr.pdf         | Bin 306669 -> 313827 bytes
 tcr.tex         |   1 +
 3 files changed, 8 insertions(+)

(limited to 'tcr.tex')

diff --git a/graph/graph.tex b/graph/graph.tex
index 5fc725e..5982e5a 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -16,5 +16,12 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 \subsection{Artikulationspunkte und Brücken}
 \lstinputlisting{graph/articulationPoints.cpp}
 
+\subsection{Eulertouren}
+\begin{itemize}
+	\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+	\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+	\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
+\end{itemize}
+
 \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
 \lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index 345a1a7..eec39ab 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/tcr.tex b/tcr.tex
index 4328b73..3e6a0ed 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -8,6 +8,7 @@
 \usepackage{amssymb}
 
 \usepackage{enumitem}
+\setlist{nosep}
 
 \usepackage{color}
 \definecolor{darkred}{rgb}{0.72,0.07,0.07}
-- 
cgit v1.2.3


From 4663f02b5df9713ce2d75b4f19bc6ca103f2d0ce Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc57.atis-stud.uni-karlsruhe.de>
Date: Sat, 22 Nov 2014 17:10:04 +0100
Subject: eulerzyklen

---
 graph/euler.cpp |  41 +++++++++++++++++++++++++++++++++++++++++
 graph/graph.tex |   2 ++
 tcr.pdf         | Bin 313827 -> 313603 bytes
 tcr.tex         |   7 ++++++-
 4 files changed, 49 insertions(+), 1 deletion(-)
 create mode 100644 graph/euler.cpp

(limited to 'tcr.tex')

diff --git a/graph/euler.cpp b/graph/euler.cpp
new file mode 100644
index 0000000..74b3399
--- /dev/null
+++ b/graph/euler.cpp
@@ -0,0 +1,41 @@
+vector< vector<int> > adjlist;
+vector< vector<int> > otherIdx;
+vector<int> cycle;
+vector<int> validIdx;
+
+void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n.
+	int neighA = adjlist[n][a];
+	int neighB = adjlist[n][b];
+	int idxNeighA = otherIdx[n][a];
+	int 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;
+}
+
+void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante).
+	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]++;
+}
+
+//findet Eulerzyklus an Knoten n startend
+//teste vorher, dass Graph zusammenhaengend ist! (isolierte Punkte sind ok)
+//teste vorher, ob Eulerzyklus ueberhaupt existiert!
+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 am Ende in cycle
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index 5982e5a..fada803 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -21,7 +21,9 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 	\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
 	\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
 	\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
+	\item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher.
 \end{itemize}
+\lstinputlisting{graph/euler.cpp}
 
 \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
 \lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index eec39ab..c735878 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/tcr.tex b/tcr.tex
index 3e6a0ed..cea7d08 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -44,13 +44,18 @@
 
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry}
 
+\usepackage{multicol}
+
 \title{Team Contest Reference}
 \author{ChaosKITs \\ Karlsruhe Institute of Technology}
 
 \begin{document}
 
 \maketitle
-\tableofcontents
+\setlength{\columnsep}{1cm}
+\begin{multicols}{2}
+	\tableofcontents
+\end{multicols}
 \newpage
 
 \input{datastructures/datastructures}
-- 
cgit v1.2.3

