From 57d99fb1601940a45aea30037396ddf0fb7c9c3d Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 15 Feb 2025 14:48:08 +0100 Subject: shorten sccs and collect scc lists --- content/graph/scc.cpp | 25 +++++++++---------------- 1 file changed, 9 insertions(+), 16 deletions(-) (limited to 'content/graph') 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> adj; -int counter, sccCounter; -vector inStack; -vector low, idx, s; //idx enthält Index der SCC pro Knoten. +vector low, idx, s; // idx enthält Index der SCC pro Knoten +vector> 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); }} -- cgit v1.2.3