diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/reroot.cpp | 53 | ||||
| -rw-r--r-- | graph/scc.cpp | 3 | ||||
| -rw-r--r-- | graph/virtualTree.cpp | 13 |
3 files changed, 34 insertions, 35 deletions
diff --git a/graph/reroot.cpp b/graph/reroot.cpp index eeca43e..4c6a748 100644 --- a/graph/reroot.cpp +++ b/graph/reroot.cpp @@ -1,39 +1,39 @@ // Usual Tree DP can be broken down in 4 steps: // - Initialize dp[v] = identity // - Iterate over all children w and take a value for w -// by looking at dp[w] and possibly the edge label of v -> w +// by looking at dp[w] and possibly the edge label of v -> w // - combine the values of those children -// usually, this operation should be commutative and associative -// - finalize the value of dp[v] after iterating over all children -struct Reroot{ +// usually this operation should be commutative and associative +// - finalize the dp[v] after iterating over all children +struct Reroot { using T = ll; // identity element - T E(){} + T E() {} // x: dp value of child // e: index of edge going to child - T takeChild(T x, int e){} - T combine(T x, T y){} + T takeChild(T x, int e) {} + T comb(T x, T y) {} // called after combining all dp values of children - T finalize(T x, int v){} + T fin(T x, int v) {} vector<vector<pair<int, int>>> g; vector<int> ord, pae; vector<T> dp; - T dfs(int v){ + T dfs(int v) { ord.push_back(v); - for(auto [w, e] : g[v]){ + for (auto [w, e] : g[v]) { g[w].erase(find(all(g[w]), pair(v, e^1))); pae[w] = e^1; - dp[v] = combine(dp[v], takeChild(dfs(w), e)); + dp[v] = comb(dp[v], takeChild(dfs(w), e)); } - return dp[v] = finalize(dp[v], v); + return dp[v] = fin(dp[v], v); } - vector<T> solve(int n, vector<pair<int, int>> edges){ + vector<T> solve(int n, vector<pair<int, int>> edges) { g.resize(n); - for(int i = 0; i < n-1; i++){ + for (int i = 0; i < n-1; i++) { g[edges[i].first].emplace_back(edges[i].second, 2*i); g[edges[i].second].emplace_back(edges[i].first, 2*i+1); } @@ -41,19 +41,22 @@ struct Reroot{ dp.assign(n, E()); dfs(0); vector<T> updp(n, E()), res(n, E()); - for(int v : ord){ + for (int v : ord) { vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1); - if(v != 0) pref[0] = takeChild(updp[v], pae[v]); - for(int i = 0; i < sz(g[v]); i++){ - pref[i+1] = suff[i] = takeChild(dp[g[v][i].first], g[v][i].second); - pref[i+1] = combine(pref[i], pref[i+1]); + if (v != 0) pref[0] = takeChild(updp[v], pae[v]); + for (int i = 0; i < sz(g[v]); i++){ + auto [u, w] = g[v][i]; + pref[i+1] = suff[i] = takeChild(dp[u], w); + pref[i+1] = comb(pref[i], pref[i+1]); } - for(int i = sz(g[v])-1; i >= 0; i--) - suff[i] = combine(suff[i], suff[i+1]); - for(int i = 0; i < sz(g[v]); i++) - updp[g[v][i].first] = finalize(combine(pref[i], suff[i+1]), v); - res[v] = finalize(pref.back(), v); + for (int i = sz(g[v])-1; i >= 0; i--) { + suff[i] = comb(suff[i], suff[i+1]); + } + for (int i = 0; i < sz(g[v]); i++) { + updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); + } + res[v] = fin(pref.back(), v); } return res; } -};
\ No newline at end of file +}; diff --git a/graph/scc.cpp b/graph/scc.cpp index 1716add..5aa7cf2 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,8 +1,7 @@ vector<vector<int>> adj, sccs; int counter, sccCounter; vector<bool> inStack; -// idx enthält den Index der SCC pro Knoten. -vector<int> low, idx, s; +vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp index f7a3cb1..2fcea80 100644 --- a/graph/virtualTree.cpp +++ b/graph/virtualTree.cpp @@ -1,10 +1,8 @@ // needs dfs in- and out- time and lca function vector<int> in, out; -void virtualTree(const vector<int>& a) { // takes indices of used nodes - auto ind = a; +void virtualTree(vector<int> ind) { // indices of used nodes sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - for (int i=0; i<sz(a)-1; i++) { ind.push_back(lca(ind[i], ind[i+1])); } @@ -13,13 +11,12 @@ void virtualTree(const vector<int>& a) { // takes indices of used nodes int n = ind.size(); vector<vector<int>> tree(n); - stack<int> st{{0}}; + vector<int> st = {0}; for (int i=1; i<n; i++) { - while (in[ind[i]] >= out[ind[st.top()]]) st.pop(); - tree[st.top()].push_back(i); + while (in[ind[i]] >= out[ind[st.back()]]) st.pop_back(); + tree[st.back()].push_back(i); st.push(i); } - // virtual directed tree with n nodes, original indices in ind - // weights can be calculated if necessary, e.g. with binary lifting + // weights can be calculated, e.g. with binary lifting } |