From 0550627fade1c01d6b90907de198ca13d34db9d9 Mon Sep 17 00:00:00 2001
From: pjungeblut <paul.jungeblut@gmail.com>
Date: Sun, 26 Oct 2014 13:02:53 +0100
Subject: adding 2-SAT

---
 sonstiges/2sat.cpp      |  63 ++++++++++++++++++++++++++++++++++++++++++++++++
 sonstiges/sonstiges.tex |   4 +++
 tcr.pdf                 | Bin 45111 -> 81835 bytes
 tcr.tex                 |  34 ++++++++++++++++----------
 4 files changed, 88 insertions(+), 13 deletions(-)
 create mode 100644 sonstiges/2sat.cpp
 create mode 100644 sonstiges/sonstiges.tex

diff --git a/sonstiges/2sat.cpp b/sonstiges/2sat.cpp
new file mode 100644
index 0000000..627e484
--- /dev/null
+++ b/sonstiges/2sat.cpp
@@ -0,0 +1,63 @@
+vector< vector<int> > adjlist; //adjazenzliste
+vector<int> sccs; //speichert die gefundenen SCCs
+vector<bool> visited; //welcher Knoten ist schon besucht worden (in der DFS)
+vector<bool> inStack; //ist Knoten gerade im Stack
+vector<int> d; //discovery time
+vector<int> low; //wie weit hoch geht's im Tiefensuchbaum
+int counter; //Zaehler fuer discovery time
+stack<int> st; //der Stack
+int sccCounter; //Zaehler fuer SCCs
+
+//Tiefensuche, die starke Zusammenhangskomponenten findet
+void visit(int v) {
+	visited[v] = true;
+	d[v] = counter;
+	low[v] = counter;
+	counter++;
+	st.push(v);
+	inStack[v] = true;
+	
+	for (int i = 0; i < (int)adjlist[v].size(); i++) {
+		int w = adjlist[v][i];
+		
+		if (!visited[w]) {
+			visit(w);
+			low[v] = min(low[v], low[w]);
+		} else if (inStack[w]) {
+			low[v] = min(low[v], low[w]);
+		}
+	}
+	
+	if (low[v] == d[v]) {
+		int next;
+		do {
+			next = st.top();
+			st.pop();
+			sccs[next] = sccCounter;
+			inStack[next] = false;
+		} while (next != v);
+		
+		sccCounter++;
+	}
+}
+
+void solve() {
+	//adjlist initialisieren
+	//(a || b) wird zu (!a => b) und (!b => a)
+	
+	visited.clear(); visited.assign(adjlist.size(), false);
+	inStack.clear(); inStack.assign(adjlist.size(), false);
+	d.clear(); d.assign(adjlist.size(), false);
+	low.clear(); low.assign(adjlist.size(), false);
+	sccs.clear(); sccs.resize(adjlist.size());
+	
+	counter = 0;
+	sccCounter = 0;
+	for (i = 0; i < (int)adjlist.size(); i++) {
+		if (!visited[i]) {
+			visit(i);
+			sccCounter++;
+		}
+	}
+	// genau dann loesbar, wenn keine Variable in gleicher SCC wie Negation ist
+}
\ No newline at end of file
diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex
new file mode 100644
index 0000000..0befff3
--- /dev/null
+++ b/sonstiges/sonstiges.tex
@@ -0,0 +1,4 @@
+\section{Sonstiges}
+
+\subsection{2-SAT}
+\lstinputlisting{sonstiges/2sat.cpp}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index 1996e3e..db1ab6c 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/tcr.tex b/tcr.tex
index cdb37b1..11aeecf 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -18,19 +18,19 @@
 \usepackage{listings}
 \lstset{
 	language={C++},
-    	numbers=left,
-     	stepnumber=1,
-     	numbersep=6pt,
-     	numberstyle=\footnotesize,
-     	breaklines=true,
-     	breakautoindent=true,
-     	breakatwhitespace=false,
-     	postbreak=\space,
-     	tabsize=2,
-     	basicstyle=\ttfamily\footnotesize,
-     	showspaces=false,
-     	showstringspaces=false,
-     	extendedchars=true,
+	numbers=left,
+	stepnumber=1,
+	numbersep=6pt,
+	numberstyle=\footnotesize,
+	breaklines=true,
+	breakautoindent=true,
+	breakatwhitespace=false,
+	postbreak=\space,
+	tabsize=2,
+	basicstyle=\ttfamily\footnotesize,
+	showspaces=false,
+	showstringspaces=false,
+	extendedchars=true,
 	keywordstyle=\color{blue}\bfseries,
 	stringstyle=\color{darkred},
 	commentstyle=\color{darkgreen}
@@ -38,9 +38,17 @@
 
 \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry}
 
+\title{Team Contest Reference}
+\author{ChaosKITs \\ Karlsruhe Institute of Technology}
+
 \begin{document}
 
+\maketitle
+\tableofcontents
+\newpage
+
 \input{maxFlow/maxFlow}
 \input{geometry/geometry}
+\input{sonstiges/sonstiges}
 
 \end{document}
\ No newline at end of file
-- 
cgit v1.2.3