diff options
| -rw-r--r-- | content/graph/scc.cpp | 19 | ||||
| -rw-r--r-- | test/graph/scc.cpp | 12 |
2 files changed, 10 insertions, 21 deletions
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index ac9a40b..32f1099 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -1,11 +1,12 @@ -vector<vector<int>> adj, sccs; -int counter; +vector<vector<int>> adj; +int counter, sccCounter; vector<bool> inStack; vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; - s.push_back(v); inStack[v] = true; + s.push_back(v); + inStack[v] = true; for (auto u : adj[v]) { if (low[u] < 0) visit(u); @@ -13,20 +14,20 @@ void visit(int v) { } if (old == low[v]) { - sccs.push_back({}); + sccCounter++; for (int u = -1; u != v;) { - u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sz(sccs) - 1; - sccs.back().push_back(u); + u = s.back(); + s.pop_back(); + inStack[u] = false; + idx[u] = sccCounter - 1; }}} void scc() { inStack.assign(sz(adj), false); low.assign(sz(adj), -1); idx.assign(sz(adj), -1); - sccs.clear(); - counter = 0; + counter = sccCounter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index 123050f..9ab7051 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -16,18 +16,6 @@ void stress_test() { }); scc(); - vector<bool> tmp(n); - for (int i = 0; i < sz(sccs); i++) { - for (int x : sccs[i]) { - if (tmp[x]) cerr << "error: duclicate" << FAIL; - if (idx[x] != i) cerr << "error: inconsistent" << FAIL; - tmp[x] = true; - } - } - for (int i = 0; i < n; i++) { - if (!tmp[i]) cerr << "error: missing" << FAIL; - } - init(n); vector<ll> seen(n); int tmpCounter = 0; |