diff options
| -rw-r--r-- | graph/havelHakimi.cpp | 4 | ||||
| -rw-r--r-- | graph/scc.cpp | 15 | ||||
| -rw-r--r-- | tcr.pdf | bin | 664992 -> 665092 bytes |
3 files changed, 9 insertions, 10 deletions
diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp index 6246fe0..cbd6991 100644 --- a/graph/havelHakimi.cpp +++ b/graph/havelHakimi.cpp @@ -1,6 +1,8 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) { priority_queue<pair<int, int>> pq; - for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i}); + for (int i = 0; i < sz(deg); i++) { + if (deg[i] > 0) pq.push({deg[i], i}); + } vector<vector<int>> adj; while (!pq.empty()) { auto [degV, v] = pq.top(); pq.pop(); diff --git a/graph/scc.cpp b/graph/scc.cpp index 5aa7cf2..ac9a40b 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,5 +1,5 @@ vector<vector<int>> adj, sccs; -int counter, sccCounter; +int counter; vector<bool> inStack; vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten. @@ -14,14 +14,11 @@ void visit(int v) { if (old == low[v]) { sccs.push_back({}); - int u; - do { + for (int u = -1; u != v;) { u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sccCounter; - sccs[sccCounter].push_back(u); - } while (u != v); - sccCounter++; -}} + idx[u] = sz(sccs) - 1; + sccs.back().push_back(u); +}}} void scc() { inStack.assign(sz(adj), false); @@ -29,7 +26,7 @@ void scc() { idx.assign(sz(adj), -1); sccs.clear(); - counter = sccCounter = 0; + counter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} Binary files differ |