From ca740ed7caeca4deb09a2fc7912f599555442e15 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc57.atis-stud.uni-karlsruhe.de>
Date: Sat, 22 Nov 2014 11:46:50 +0100
Subject: bisschen LGS

---
 math/math.tex | 7 +++++++
 1 file changed, 7 insertions(+)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index f82ab65..db42b74 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -15,6 +15,13 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 	\end{itemize}
 	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
 \end{description}
+\lstinputlisting{math/multInv.cpp}
+
+\subsubsection{Mod-Exponent über $\mathbb{F}_p$}
+\lstinputlisting{math/modExp.cpp}
+
+\subsection{LGS über $\mathbb{F}_p$}
+\lstinputlisting{math/lgsFp.cpp}
 
 \subsection{Binomialkoeffizienten}
 \lstinputlisting{math/binomial.cpp}
\ No newline at end of file
-- 
cgit v1.2.3


From 44921d90e48ff259926d9173eaf4dd975e001424 Mon Sep 17 00:00:00 2001
From: kittobi1992 <kittobi1992@users.noreply.github.com>
Date: Sat, 22 Nov 2014 12:18:05 +0100
Subject: Update math.tex

update math.tex
---
 math/math.tex | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index db42b74..71e5648 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -17,6 +17,13 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 \end{description}
 \lstinputlisting{math/multInv.cpp}
 
+
+\subsubsection{Primzahlsieb von Eratosthenes}
+\lstinputlisting{math/primeSieve.cpp}
+
+\subsubsection{Faktorisierung}
+\lstinputlisting{math/factor.cpp}
+
 \subsubsection{Mod-Exponent über $\mathbb{F}_p$}
 \lstinputlisting{math/modExp.cpp}
 
@@ -24,4 +31,4 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 \lstinputlisting{math/lgsFp.cpp}
 
 \subsection{Binomialkoeffizienten}
-\lstinputlisting{math/binomial.cpp}
\ No newline at end of file
+\lstinputlisting{math/binomial.cpp}
-- 
cgit v1.2.3


From 9fe234e7181b1cad9652655e674e7f9f821814b7 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc57.atis-stud.uni-karlsruhe.de>
Date: Sat, 22 Nov 2014 12:50:19 +0100
Subject: Artikulationpunkte

---
 graph/articulationPoints.cpp |  47 +++++++++++++++++++++++++++++++++++++++++++
 graph/graph.tex              |   3 +++
 math/math.tex                |   7 +++----
 tcr.pdf                      | Bin 291824 -> 297317 bytes
 4 files changed, 53 insertions(+), 4 deletions(-)
 create mode 100644 graph/articulationPoints.cpp

(limited to 'math/math.tex')

diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
new file mode 100644
index 0000000..b99a286
--- /dev/null
+++ b/graph/articulationPoints.cpp
@@ -0,0 +1,47 @@
+vector< vector<int> > adjlist;
+vector<int> low;
+vector<int> d;
+vector<bool> isArtPoint;
+vector< vector<int> > bridges; //nur fuer Bruecken
+int counter = 0;
+
+void visit(int v, int parent) {
+	d[v] = low[v] = ++counter;
+	int numVisits = 0, maxlow = 0;
+	
+	for (vector<int>::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) {
+		if (d[*vit] == 0) {
+			numVisits++;
+			visit(*vit, v);
+			if (low[*vit] > maxlow) {
+				maxlow = low[*vit];
+			}
+			
+			if (low[*vit] > d[v]) { //nur fuer Bruecken
+				bridges[v].push_back(*vit); bridges[*vit].push_back(v);
+			}
+			
+			low[v] = min(low[v], low[*vit]);
+		} else {
+			if (d[*vit] < low[v]) {
+				low[v] = d[*vit];
+			}
+		}
+	}
+	
+	if (parent == -1) {
+		if (numVisits > 1) isArtPoint[v] = true;
+	} else {
+		if (maxlow >= d[v]) isArtPoint[v] = true;
+	}
+}
+
+void findArticulationPoints() {
+	low.clear(); low.resize(adjlist.size());
+	d.clear(); d.assign(adjlist.size(), 0);
+	isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false);
+	bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken
+	for (int v = 0; v < (int)adjlist.size(); v++) {
+		if (d[v] == 0) visit(v, -1);
+	}
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index 2bf395c..5fc725e 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -13,5 +13,8 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
+\subsection{Artikulationspunkte und Brücken}
+\lstinputlisting{graph/articulationPoints.cpp}
+
 \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
 \lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
diff --git a/math/math.tex b/math/math.tex
index 71e5648..973103a 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -17,10 +17,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 \end{description}
 \lstinputlisting{math/multInv.cpp}
 
-
-\subsubsection{Primzahlsieb von Eratosthenes}
-\lstinputlisting{math/primeSieve.cpp}
-
 \subsubsection{Faktorisierung}
 \lstinputlisting{math/factor.cpp}
 
@@ -32,3 +28,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 
 \subsection{Binomialkoeffizienten}
 \lstinputlisting{math/binomial.cpp}
+
+\subsection{Primzahlsieb von Eratosthenes}
+\lstinputlisting{math/primeSieve.cpp}
diff --git a/tcr.pdf b/tcr.pdf
index 8a59d24..c4e7d62 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3

