merge

7 files changed, 30 insertions, 45 deletions

diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp
index 1332a4a..11ae2f7 100644
--- a/content/geometry/polygon.cpp
+++ b/content/geometry/polygon.cpp
@@ -23,7 +23,7 @@ ll windingNumber(pt p, const vector<pt>& poly) {
 	return res;
 }
 
-// check if point is inside polygon (any polygon)
+// check if p is inside poly (any polygon poly[0] == poly.back())
 bool inside(pt p, const vector<pt>& poly) {
 	bool in = false;
 	for (int i = 0; i + 1 < sz(poly); i++) {
diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index 0974b78..b0828d0 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -43,6 +43,7 @@ ll dfs(int v, ll flow) {
 ll maxFlow(int source, int target) {
 	s = source, t = target;
 	ll flow = 0;
+	// set lim = 1 and use dfs(s, INF) to disable scaling
 	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
 		while (bfs(lim)) {
 			pt.assign(sz(adj), 0);
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index 213c597..eb12cdb 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -111,6 +111,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\begin{methods}
 		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
 	\end{methods}
+	\textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge!
 	\sourcecode{graph/scc.cpp}
 \end{algorithm}
 
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index 32f1099..a6af7d6 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,33 +1,27 @@
 vector<vector<int>> adj;
-int counter, sccCounter;
-vector<bool> inStack;
+int sccCounter;
 vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
 
 void visit(int v) {
-	int old = low[v] = counter++;
+	int old = low[v] = sz(s);
 	s.push_back(v);
-	inStack[v] = true;
 
 	for (auto u : adj[v]) {
 		if (low[u] < 0) visit(u);
-		if (inStack[u]) low[v] = min(low[v], low[u]);
+		if (idx[u] < 0) low[v] = min(low[v], low[u]);
 	}
 
 	if (old == low[v]) {
+		for (int i = old; i < sz(s); i++) idx[s[i]] = sccCounter;
 		sccCounter++;
-		for (int u = -1; u != v;) {
-			u = s.back();
-			s.pop_back();
-			inStack[u] = false;
-			idx[u] = sccCounter - 1;
-}}}
+		s.resize(old);
+}}
 
 void scc() {
-	inStack.assign(sz(adj), false);
 	low.assign(sz(adj), -1);
 	idx.assign(sz(adj), -1);
 
-	counter = sccCounter = 0;
+	sccCounter = 0;
 	for (int i = 0; i < sz(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/content/other/other.tex b/content/other/other.tex
index 191a6da..a38f6da 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -147,7 +147,7 @@
 	Im Residualgraphen:

 	\begin{itemize}

 		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}

-		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{erreichbar} sind.

+		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{s} erreichbar sind.

 	\end{itemize}

 

 	\item \textbf{Allgemeiner Graph:}

@@ -156,7 +156,7 @@
 

 	\item \textbf{Bipartiter Graph:}

 	Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.

-	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, makiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die makierten Knoten aus $B$ und die unmakierten Knoten aus $A$.

+	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.

 

 	\item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:}

 	Minimiere Matchinggewicht.

diff --git a/tcr.pdf b/tcr.pdf
index 76c898a..6b38da9 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp
index 9ab7051..cf4efc7 100644
--- a/test/graph/scc.cpp
+++ b/test/graph/scc.cpp
@@ -1,6 +1,5 @@
 #include "../util.h"
 #include <graph/scc.cpp>
-#include <datastructures/unionFind.cpp>
 
 void stress_test() {
 	ll queries = 0;
@@ -16,37 +15,27 @@ void stress_test() {
 		});
 		scc();
 
-		init(n);
-		vector<ll> seen(n);
-		int tmpCounter = 0;
-		auto reach = [&](int a, int b) {
-			tmpCounter++;
-			seen[a] = tmpCounter;
-			vector<int> todo = {a};
-			while (seen[b] != tmpCounter && !todo.empty()) {
-				a = todo.back();
-				todo.pop_back();
-				g.forOut(a, [&](int /**/, int x){
-					if (seen[x] != tmpCounter) {
-						seen[x] = tmpCounter;
-						todo.push_back(x);
-					}
+		auto reach = [&](int a) -> vector<bool> {
+			vector<bool> seen(n);
+			auto dfs = [&](auto &&self, int u) -> void {
+				if (seen[u]) return;
+				seen[u] = true;
+				g.forOut(u, [&](int, int v) {
+					self(self, v);
 				});
-			}
-			return seen[b] == tmpCounter;
+			};
+			dfs(dfs, a);
+			return seen;
 		};
-		for (int a = 0; a < n; a++) {
-			for (int b = 0; b < a; b++) {
-				if (findSet(a) == findSet(b)) continue;
-				if (reach(a, b) && reach(b, a)) unionSets(a, b);
-			}
-		}
 
 		for (int a = 0; a < n; a++) {
-			for (int b = 0; b <= a; b++) {
-				bool got = idx[a] == idx[b];
-				bool expected = findSet(a) == findSet(b);
-				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			vector<bool> reacha = reach(a);
+			for (int b = 0; b < n; b++) {
+				if (idx[a] == idx[b]) {
+					if (!reacha[b]) cerr << a << " and " << b << " should be in different SCCs" << FAIL;
+				} else if (idx[a] < idx[b]) {
+					if (reacha[b]) cerr << a << " should come before " << b << " in topological order" << FAIL;
+				}
 			}
 		}
 		queries += n;
@@ -66,7 +55,7 @@ void performance_test() {
 	});
 
 	t.start();
-	scc();	
+	scc();
 	t.stop();
 	hash_t hash = 0;
 	for (int x : idx) hash += x;