merge

5 files changed, 55 insertions, 1 deletions

diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
new file mode 100644
index 0000000..899db15
--- /dev/null
+++ b/datastructures/RMQ.cpp
@@ -0,0 +1,20 @@
+vector<int> data(RMQ_SIZE);
+vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE));
+
+void initRMQ() {
+	for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) {
+		for(int l = 0; l + s <= RMQ_SIZE; l++) {
+			if(i == 0) rmq[0][l] = l;
+			else {
+				int r = l + ss;
+				rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]);
+			}
+		}
+	}
+}
+//returns index of minimum! [a, b)
+int queryRMQ(int l, int r) {
+	if(l >= r) return l;
+	int s = floor(log2(r-l)); r = r - (1 << s);
+	return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]);
+}
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index c314400..baa4fec 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -5,3 +5,6 @@
 
 \subsection{Segmentbaum}
 \lstinputlisting{datastructures/segmentTree.cpp}
+
+\subsection{Range Minimum Query}
+\lstinputlisting{datastructures/RMQ.cpp}
diff --git a/graph/LCA.cpp b/graph/LCA.cpp
new file mode 100644
index 0000000..b4e6bdd
--- /dev/null
+++ b/graph/LCA.cpp
@@ -0,0 +1,16 @@
+//RMQ muss hinzugefuegt werden!
+vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
+vector<vector<int>> graph(MAX_N);
+
+void initLCA(int gi, int d, int &c) {
+	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
+	for(int gn : graph[gi]) {
+		initLCA(gn, d+1, c);
+		visited[c] = gi, depth[c] = d, c++;
+	}
+}
+//[a, b]
+int getLCA(int a, int b) {
+	return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))];
+}
+//=> int c = 0; initLCA(0,0,c); initRMQ(); done!
diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp
new file mode 100644
index 0000000..ee56441
--- /dev/null
+++ b/graph/floydWarshall.cpp
@@ -0,0 +1,8 @@
+//initialize adjmat, adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j
+for (k = 0; k < MAX_V; k++) {
+	for (i = 0; i < MAX_V; i++) {
+		for (j = 0; j < MAX_V; j++) {
+			if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j];
+		}
+	}
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index fada803..e3fd262 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,5 +1,8 @@
 \section{Graphen}
 
+\subsection{Lowest Common Ancestor}
+\lstinputlisting{graph/LCA.cpp}
+
 \subsection{Kürzeste Wege}
 
 \subsubsection{Algorithmus von \textsc{Dijkstra}}
@@ -10,6 +13,10 @@ Kürzeste Pfade in Graphen ohne negative Kanten.
 Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 \lstinputlisting{graph/bellmannFord.cpp}
 
+\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
+Alle kürzesten Pfade im Graphen.
+\lstinputlisting{graph/floydWarshall.cpp}
+
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
@@ -26,4 +33,4 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 \lstinputlisting{graph/euler.cpp}
 
 \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
-\lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
+\lstinputlisting{graph/edmondsKarp.cpp}