From a9d0fb392d56315139a0d2683217bc7a54bd7cce Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 21 Apr 2025 13:33:59 +0200
Subject: merge

---
 content/graph/dinicScaling.cpp |  1 +
 content/graph/graph.tex        |  1 +
 content/graph/scc.cpp          | 20 +++++++-------------
 3 files changed, 9 insertions(+), 13 deletions(-)

(limited to 'content/graph')

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