make SCC a struct, and minor 2SAT changes

2 files changed, 35 insertions, 36 deletions

diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp
index b9cfd1c..d4c8b7b 100644
--- a/content/graph/2sat.cpp
+++ b/content/graph/2sat.cpp
@@ -1,28 +1,28 @@
-constexpr int var(int i) {return i << 1;} // use this!
-struct sat2 {
-	int n; // + scc variablen
+constexpr int var(int i) { return i << 1; } // use this!
+struct SAT2 {
+	int n;
+	vector<vector<int>> adj;
 	vector<int> sol;
-	sat2(int vars) : n(vars*2), adj(n) {}
+	SAT2(int vars) : n(vars*2), adj(n) {}
 
 	void addImpl(int a, int b) {
 		adj[a].push_back(b);
 		adj[1^b].push_back(1^a);
 	}
 	void addEquiv(int a, int b) { addImpl(a, b); addImpl(b, a); }
-	void addOr(int a, int b) { addImpl(1^a, b);}
-	void addXor(int a, int b) { addOr(a, b); addOr(1^a, 1^b); }
-	void addTrue(int a) { addImpl(1^a, a);}
-	void addFalse(int a) { addTrue(1^a);}
+	void addOr(int a, int b) { addImpl(1^a, b); }
+	void addXor(int a, int b) { addEquiv(a, 1^b); }
+	void addTrue(int a) { addImpl(1^a, a); }
+	void addFalse(int a) { addTrue(1^a); }
 	void addAnd(int a, int b) { addTrue(a); addTrue(b); }
 	void addNand(int a, int b) { addOr(1^a, 1^b); }
 
 	bool solve() {
-		scc(); //scc code von oben
+		SCC scc(adj); // SCC @\sourceref{graph/scc.cpp}@
 		sol.assign(n, -1);
-		for (int i = 0; i < n; i += 2) {
-			if (idx[i] == idx[i + 1]) return false;
-			sol[i] = idx[i] < idx[i + 1];
-			sol[i + 1] = !sol[i];
+		for (int i = 0; i < n; i++) {
+			if (scc.idx[i] == scc.idx[1^i]) return false;
+			sol[i] = scc.idx[i] < scc.idx[1^i];
 		}
 		return true;
 	}
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index 9f8f850..a9e10c1 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,26 +1,25 @@
-vector<vector<int>> adj;
-vector<int> low, idx, s; // idx enthält Index der SCC pro Knoten
-vector<vector<int>> sccs; // Liste der Knoten pro SCC
+struct SCC {
+	vector<int> idx; // idx enthält Index der SCC pro Knoten
+	vector<vector<int>> sccs; // Liste der Knoten pro SCC
 
-void visit(int v) {
-	int old = low[v] = ssize(s);
-	s.push_back(v);
+	SCC(const vector<vector<int>> &adj): idx(ssize(adj), -1) {
+		vector<int> low(ssize(adj), -1);
+		vector<int> s;
+		auto dfs = [&](auto &&self, int v) -> void {
+			int old = low[v] = ssize(s);
+			s.push_back(v);
 
-	for (auto u : adj[v]) {
-		if (low[u] < 0) visit(u);
-		if (idx[u] < 0) low[v] = min(low[v], low[u]);
-	}
+			for (auto u : adj[v]) {
+				if (low[u] < 0) self(self, u);
+				if (idx[u] < 0) low[v] = min(low[v], low[u]);
+			}
 
-	if (old == low[v]) {
-		sccs.emplace_back(begin(s) + old, end(s));
-		for (int u: sccs.back()) idx[u] = ssize(sccs)-1;
-		s.resize(old);
-}}
-
-void scc() {
-	low.assign(ssize(adj), -1);
-	idx.assign(ssize(adj), -1);
-	sccs.clear();
-	for (int i = 0; i < ssize(adj); i++) {
-		if (low[i] < 0) visit(i);
-}}
+			if (old == low[v]) {
+				sccs.emplace_back(begin(s) + old, end(s));
+				for (int u: sccs.back()) idx[u] = ssize(sccs)-1;
+				s.resize(old);
+		}};
+		for (int i = 0; i < ssize(adj); i++) {
+			if (low[i] < 0) dfs(dfs, i);
+	}}
+};