diff options
Diffstat (limited to 'content/graph/scc.cpp')
| -rw-r--r-- | content/graph/scc.cpp | 19 |
1 files changed, 9 insertions, 10 deletions
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index a6af7d6..9f8f850 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -1,9 +1,9 @@ vector<vector<int>> adj; -int sccCounter; -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] = sz(s); + int old = low[v] = ssize(s); s.push_back(v); for (auto u : adj[v]) { @@ -12,16 +12,15 @@ void visit(int v) { } if (old == low[v]) { - for (int i = old; i < sz(s); i++) idx[s[i]] = sccCounter; - sccCounter++; + 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(sz(adj), -1); - idx.assign(sz(adj), -1); - - sccCounter = 0; - for (int i = 0; i < sz(adj); i++) { + 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); }} |