SCCS added, seperated from 2-SAT

3 files changed, 95 insertions, 0 deletions

diff --git a/graph/edmondsKarp.cpp b/graph/edmondsKarp.cpp
new file mode 100644
index 0000000..26c5b0d
--- /dev/null
+++ b/graph/edmondsKarp.cpp
@@ -0,0 +1,34 @@
+int s, t, f; //source, target, single flow
+int res[MAX_V][MAX_V]; //adj-matrix
+vector< vector<int> > adjList;
+int p[MAX_V]; //bfs spanning tree
+
+void augment(int v, int minEdge) {
+	if (v == s) { f = minEdge; return; }
+	else if (p[v] != -1) {
+		augment(p[v], min(minEdge, res[p[v]][v]));
+		res[p[v]][v] -= f; res[v][p[v]] += f;
+}}
+
+int maxFlow() { //first inititalize res, adjList, s and t
+	int mf = 0;
+	while (true) {
+		f = 0;
+		bitset<MAX_V> vis; vis[s] = true;
+		queue<int> q; q.push(s);
+		memset(p, -1, sizeof(p));
+		while (!q.empty()) { //BFS
+			int u = q.front(); q.pop();
+			if (u == t) break;
+			for (int j = 0; j < (int)adjList[u].size(); j++) {
+				int v = adjList[u][j];
+				if (res[u][v] > 0 && !vis[v]) {
+					vis[v] = true; q.push(v); p[v] = u;
+		}}}
+		
+		augment(t, INF); //add found path to max flow
+		if (f == 0) break;
+		mf += f;
+	}
+	return mf;
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
new file mode 100644
index 0000000..1c37bc7
--- /dev/null
+++ b/graph/graph.tex
@@ -0,0 +1,7 @@
+\section{Graph}
+
+\subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
+\lstinputlisting{graph/scc.cpp}
+
+\subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)}
+\lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file
diff --git a/graph/scc.cpp b/graph/scc.cpp
new file mode 100644
index 0000000..b33616b
--- /dev/null
+++ b/graph/scc.cpp
@@ -0,0 +1,54 @@
+int counter, sccCounter, n; //n == number of vertices
+vector<bool> visited, inStack;
+vector< vector<int> > adjlist;
+vector<int> d, low, sccs;
+stack<int> s;
+
+void visit(int v) {
+	visited[v] = true;
+	d[v] = counter;
+	low[v] = counter;
+	counter++;
+	inStack[v] = true;
+	s.push(v);
+	
+	for (int i = 0; i < (int)adjlist[v].size(); i++) {
+		int u = adjlist[v][i];
+		if (!visited[u]) {
+			visit(u);
+			low[v] = min(low[v], low[u]);
+		} else if (inStack[u]) {
+			low[v] = min(low[v], low[u]);
+		}
+	}
+	
+	if (d[v] == low[v]) {
+		int u;
+		do {
+			u = s.top();
+			s.pop();
+			inStack[u] = false;
+			sccs[u] = sccCounter;
+		} while(u != v);
+		sccCounter++;
+	}
+}
+
+void scc() {
+	//read adjlist
+	
+	visited.clear(); visited.assign(n, false);
+	d.clear(); d.resize(n);
+	low.clear(); low.resize(n);
+	inStack.clear(); inStack.assign(n, false);
+	sccs.clear(); sccs.resize(n);
+	
+	counter = 0;
+	sccCounter = 0;
+	for (i = 0; i < n; i++) {
+		if (!visited[i]) {
+			visit(i);
+		}
+	}
+	//sccs has the component for each vertex
+}
\ No newline at end of file