From 07a1c4f87dcccbfe2ca4fbbc100a07c9be801502 Mon Sep 17 00:00:00 2001
From: pjungeblut <paul.jungeblut@gmail.com>
Date: Thu, 30 Oct 2014 19:26:30 +0100
Subject: SCCS added, seperated from 2-SAT

---
 graph/scc.cpp | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
 create mode 100644 graph/scc.cpp

(limited to 'graph/scc.cpp')

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
-- 
cgit v1.2.3