shorten sccs and collect scc lists

2 files changed, 18 insertions, 16 deletions

diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index 6887712..63b2757 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,33 +1,26 @@
 vector<vector<int>> adj;
-int counter, sccCounter;
-vector<bool> inStack;
-vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
+vector<int> low, idx, s; // 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] = counter++;
+	int old = low[v] = ssize(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]) {
-		sccCounter++;
-		for (int u = -1; u != v;) {
-			u = s.back();
-			s.pop_back();
-			inStack[u] = false;
-			idx[u] = sccCounter - 1;
-}}}
+		sccs.emplace_back(begin(s) + old, end(s));
+		for (int u: sccs.back()) idx[u] = ssize(sccs)-1;
+		s.erase(begin(s) + old, end(s));
+}}
 
 void scc() {
-	inStack.assign(ssize(adj), false);
 	low.assign(ssize(adj), -1);
 	idx.assign(ssize(adj), -1);
-
-	counter = sccCounter = 0;
+	sccs.clear();
 	for (int i = 0; i < ssize(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp
index cf4efc7..46ad201 100644
--- a/test/graph/scc.cpp
+++ b/test/graph/scc.cpp
@@ -28,7 +28,16 @@ void stress_test() {
 			return seen;
 		};
 
+		vector<int> seen(n);
+		for (int i = 0; i < ssize(sccs); i++) {
+			for (int v: sccs[i]) {
+				if (idx[v] != i) cerr << v << " is in scc " << i << ", but idx[" << v << "] = " << idx[v] << FAIL;
+				seen[v]++;
+			}
+		}
+
 		for (int a = 0; a < n; a++) {
+			if (seen[a] != 1) cerr << a << " occurs " << seen[a] << " times in sccs" << FAIL;
 			vector<bool> reacha = reach(a);
 			for (int b = 0; b < n; b++) {
 				if (idx[a] == idx[b]) {