diff options
Diffstat (limited to 'content/graph')
31 files changed, 196 insertions, 160 deletions
diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp index 75e54e6..2b49fc6 100644 --- a/content/graph/2sat.cpp +++ b/content/graph/2sat.cpp @@ -4,19 +4,19 @@ struct sat2 { sat2(int vars) : n(vars*2), adj(n) {} - static int var(int i) {return i << 1;} // use this! + static int var(int i) { return i << 1; } // use this! void addImpl(int a, int b) { adj[a].push_back(b); adj[1^b].push_back(1^a); } - void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);} - void addOr(int a, int b) {addImpl(1^a, b);} - void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);} - void addTrue(int a) {addImpl(1^a, a);} - void addFalse(int a) {addTrue(1^a);} - void addAnd(int a, int b) {addTrue(a); addTrue(b);} - void addNand(int a, int b) {addOr(1^a, 1^b);} + void addEquiv(int a, int b) { addImpl(a, b); addImpl(b, a); } + void addOr(int a, int b) { addImpl(1^a, b);} + void addXor(int a, int b) { addOr(a, b); addOr(1^a, 1^b); } + void addTrue(int a) { addImpl(1^a, a);} + void addFalse(int a) { addTrue(1^a);} + void addAnd(int a, int b) { addTrue(a); addTrue(b); } + void addNand(int a, int b) { addOr(1^a, 1^b); } bool solve() { scc(); //scc code von oben diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index 221b5ed..1da8876 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -5,12 +5,12 @@ struct LCA { SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector<vector<int>>& adj, int root) { - depth.assign(2 * sz(adj), 0); - visited.assign(2 * sz(adj), -1); - first.assign(sz(adj), 2 * sz(adj)); + depth.assign(2 * ssize(adj), 0); + visited.assign(2 * ssize(adj), -1); + first.assign(ssize(adj), 2 * ssize(adj)); idx = 0; dfs(adj, root); - st.init(&depth); + st.init(depth); } void dfs(vector<vector<int>>& adj, int v, ll d=0) { @@ -18,15 +18,15 @@ struct LCA { first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { - if (first[u] == 2 * sz(adj)) { + if (first[u] == 2 * ssize(adj)) { dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} int getLCA(int u, int v) { if (first[u] > first[v]) swap(u, v); - return visited[st.queryIdempotent(first[u], first[v] + 1)]; + return visited[st.query(first[u], first[v] + 1)]; } - ll getDepth(int v) {return depth[first[v]];} + ll getDepth(int v) { return depth[first[v]]; } }; diff --git a/content/graph/TSP.cpp b/content/graph/TSP.cpp index 6223858..4d2479c 100644 --- a/content/graph/TSP.cpp +++ b/content/graph/TSP.cpp @@ -1,7 +1,7 @@ vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten. auto TSP() { - int n = sz(dist), m = 1 << n; + int n = ssize(dist), m = 1 << n; vector<vector<edge>> dp(n, vector<edge>(m, edge{INF, -1})); for (int c = 0; c < n; c++) @@ -21,7 +21,7 @@ auto TSP() { vector<int> tour = {0}; int v = 0; - while (tour.back() != 0 || sz(tour) == 1) + while (tour.back() != 0 || ssize(tour) == 1) tour.push_back(dp[tour.back()] [(v |= (1 << tour.back()))].to); // Enthält Knoten 0 zweimal. An erster und letzter Position. diff --git a/content/graph/articulationPoints.cpp b/content/graph/articulationPoints.cpp index 25ff67e..60970e6 100644 --- a/content/graph/articulationPoints.cpp +++ b/content/graph/articulationPoints.cpp @@ -14,14 +14,14 @@ int dfs(int v, int from = -1) { if (num[e.to] < me) st.push_back(e); } else { if (v == root) rootCount++; - int si = sz(st); + int si = ssize(st); int up = dfs(e.to, e.id); top = min(top, up); if (up >= me) isArt[v] = true; if (up > me) bridges.push_back(e); if (up <= me) st.push_back(e); if (up == me) { - bcc.emplace_back(si + all(st)); + bcc.emplace_back(begin(st) + si, end(st)); st.resize(si); }}} return top; @@ -29,12 +29,12 @@ int dfs(int v, int from = -1) { void find() { counter = 0; - num.assign(sz(adj), 0); - isArt.assign(sz(adj), false); + num.assign(ssize(adj), 0); + isArt.assign(ssize(adj), false); bridges.clear(); st.clear(); bcc.clear(); - for (int v = 0; v < sz(adj); v++) { + for (int v = 0; v < ssize(adj); v++) { if (!num[v]) { root = v; rootCount = 0; diff --git a/content/graph/binary_lifting.cpp b/content/graph/binary_lifting.cpp new file mode 100644 index 0000000..f88b1a9 --- /dev/null +++ b/content/graph/binary_lifting.cpp @@ -0,0 +1,28 @@ +struct Lift { + vector<int> dep, par, jmp; + + Lift(vector<vector<int>> &adj, int root): + dep(adj.size()), par(adj.size()), jmp(adj.size(), root) { + auto dfs = [&](auto &self, int u, int p, int d) -> void { + dep[u] = d, par[u] = p; + jmp[u] = dep[p] + dep[jmp[jmp[p]]] == 2*dep[jmp[p]] + ? jmp[jmp[p]] : p; + for (int v: adj[u]) if (v != p) self(self, v, u, d+1); + }; + dfs(dfs, root, root, 0); + } + + int depth(int v) { return dep[v]; } + int lift(int v, int d) { + while (dep[v] > d) v = dep[jmp[v]] < d ? par[v] : jmp[v]; + return v; + } + int lca(int u, int v) { + v = lift(v, dep[u]), u = lift(u, dep[v]); + while (u != v) { + auto &a = jmp[u] == jmp[v] ? par : jmp; + u = a[u], v = a[v]; + } + return u; + } +}; diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index eee5082..eeff156 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -1,10 +1,10 @@ vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten. auto bitonicTSP() { - vector<double> dp(sz(dist), HUGE_VAL); - vector<int> pre(sz(dist)); // nur für Tour + vector<double> dp(ssize(dist), HUGE_VAL); + vector<int> pre(ssize(dist)); // nur für Tour dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0; - for (unsigned int i = 2; i < sz(dist); i++) { + for (unsigned int i = 2; i < ssize(dist); i++) { double link = 0; for (int j = i - 2; j >= 0; j--) { link += dist[j + 1][j + 2]; @@ -13,9 +13,9 @@ auto bitonicTSP() { dp[i] = opt; pre[i] = j; }}} - // return dp.back(); // Länger der Tour + // return dp.back(); // Länge der Tour - int j, n = sz(dist) - 1; + int j, n = ssize(dist) - 1; vector<int> ut, lt = {n, n - 1}; do { j = pre[n]; @@ -25,7 +25,7 @@ auto bitonicTSP() { } } while(n = j + 1, j > 0); (lt.back() == 1 ? lt : ut).push_back(0); - reverse(all(lt)); - lt.insert(lt.end(), all(ut)); + ranges::reverse(lt); + lt.insert(end(lt), begin(ut), end(ut)); return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp index cacfb9c..b6d72d8 100644 --- a/content/graph/bitonicTSPsimple.cpp +++ b/content/graph/bitonicTSPsimple.cpp @@ -3,7 +3,7 @@ vector<vector<double>> dp; double get(int p1, int p2) { int v = max(p1, p2) + 1; - if (v == sz(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; + if (v == ssize(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; if (dp[p1][p2] >= 0.0) return dp[p1][p2]; double tryLR = dist[p1][v] + get(v, p2); double tryRL = dist[p2][v] + get(p1, v); @@ -11,17 +11,19 @@ double get(int p1, int p2) { } auto bitonicTSP() { - dp = vector<vector<double>>(sz(dist), - vector<double>(sz(dist), -1)); + dp = vector<vector<double>>(ssize(dist), + vector<double>(ssize(dist), -1)); get(0, 0); - // return dp[0][0]; // Länger der Tour + // return dp[0][0]; // Länge der Tour vector<int> lr = {0}, rl = {0}; - for (int p1 = 0, p2 = 0, v; (v = max(p1, p2)+1) < sz(dist);) { + for (int p1 = 0, p2 = 0, v; + (v = max(p1, p2)+1) < ssize(dist);) { if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { lr.push_back(v); p1 = v; } else { rl.push_back(v); p2 = v; }} lr.insert(lr.end(), rl.rbegin(), rl.rend()); - return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. + // Enthält Knoten 0 zweimal. An erster und letzter Position. + return lr; } diff --git a/content/graph/blossom.cpp b/content/graph/blossom.cpp index 7bd494a..3c9bd31 100644 --- a/content/graph/blossom.cpp +++ b/content/graph/blossom.cpp @@ -32,7 +32,7 @@ struct GM { auto h = label[r] = label[s] = {~x, y}; int join; while (true) { - if (s != sz(adj)) swap(r, s); + if (s != ssize(adj)) swap(r, s); r = findFirst(label[pairs[r]].first); if (label[r] == h) { join = r; @@ -48,13 +48,13 @@ struct GM { }}} bool augment(int v) { - label[v] = {sz(adj), -1}; - first[v] = sz(adj); + label[v] = {ssize(adj), -1}; + first[v] = ssize(adj); head = tail = 0; for (que[tail++] = v; head < tail;) { int x = que[head++]; for (int y : adj[x]) { - if (pairs[y] == sz(adj) && y != v) { + if (pairs[y] == ssize(adj) && y != v) { pairs[y] = x; rematch(x, y); return true; @@ -70,12 +70,12 @@ struct GM { int match() { int matching = head = tail = 0; - for (int v = 0; v < sz(adj); v++) { - if (pairs[v] < sz(adj) || !augment(v)) continue; + for (int v = 0; v < ssize(adj); v++) { + if (pairs[v] < ssize(adj) || !augment(v)) continue; matching++; for (int i = 0; i < tail; i++) label[que[i]] = label[pairs[que[i]]] = {-1, -1}; - label[sz(adj)] = {-1, -1}; + label[ssize(adj)] = {-1, -1}; } return matching; } diff --git a/content/graph/bronKerbosch.cpp b/content/graph/bronKerbosch.cpp index 0cfcc5f..cf07c88 100644 --- a/content/graph/bronKerbosch.cpp +++ b/content/graph/bronKerbosch.cpp @@ -11,7 +11,7 @@ void bronKerboschRec(bits R, bits P, bits X) { } else { int q = min(P._Find_first(), X._Find_first()); bits cands = P & ~adj[q]; - for (int i = 0; i < sz(adj); i++) if (cands[i]) { + for (int i = 0; i < ssize(adj); i++) if (cands[i]) { R[i] = 1; bronKerboschRec(R, P & adj[i], X & adj[i]); R[i] = P[i] = 0; @@ -20,5 +20,5 @@ void bronKerboschRec(bits R, bits P, bits X) { void bronKerbosch() { cliques.clear(); - bronKerboschRec({}, {(1ull << sz(adj)) - 1}, {}); + bronKerboschRec({}, {(1ull << ssize(adj)) - 1}, {}); } diff --git a/content/graph/centroid.cpp b/content/graph/centroid.cpp index 820945b..3cd5519 100644 --- a/content/graph/centroid.cpp +++ b/content/graph/centroid.cpp @@ -15,7 +15,7 @@ pair<int, int> dfs_cent(int v, int from, int n) { } pair<int, int> find_centroid(int root = 0) { - s.resize(sz(adj)); + s.resize(ssize(adj)); dfs_sz(root); return dfs_cent(root, -1, s[root]); } diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp index 6a299ee..deac71e 100644 --- a/content/graph/cycleCounting.cpp +++ b/content/graph/cycleCounting.cpp @@ -9,8 +9,8 @@ struct cycles { cycles(int n) : adj(n), seen(n), paths(n) {} void addEdge(int u, int v) { - adj[u].push_back({v, sz(edges)}); - adj[v].push_back({u, sz(edges)}); + adj[u].push_back({v, ssize(edges)}); + adj[v].push_back({u, ssize(edges)}); edges.push_back({u, v}); } @@ -36,10 +36,10 @@ struct cycles { cur[id].flip(); }}} - bool isCycle(cycle cur) {//cycle must be constrcuted from base + bool isCycle(cycle cur) {// cycle must be constructed from base if (cur.none()) return false; - init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ - for (int i = 0; i < sz(edges); i++) { + init(ssize(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ + for (int i = 0; i < ssize(edges); i++) { if (cur[i]) { cur[i] = false; if (findSet(edges[i].first) == @@ -50,12 +50,12 @@ struct cycles { } int count() { - for (int i = 0; i < sz(adj); i++) findBase(i); - assert(sz(base) < 30); + for (int i = 0; i < ssize(adj); i++) findBase(i); + assert(ssize(base) < 30); int res = 0; - for (int i = 1; i < (1 << sz(base)); i++) { + for (int i = 1; i < (1 << ssize(base)); i++) { cycle cur; - for (int j = 0; j < sz(base); j++) + for (int j = 0; j < ssize(base); j++) if (((i >> j) & 1) != 0) cur ^= base[j]; if (isCycle(cur)) res++; } diff --git a/content/graph/dijkstra.cpp b/content/graph/dijkstra.cpp index 61c636d..ab4bef9 100644 --- a/content/graph/dijkstra.cpp +++ b/content/graph/dijkstra.cpp @@ -1,21 +1,18 @@ -using path = pair<ll, int>; //dist, destination +using Dist = ll; -auto dijkstra(const vector<vector<path>>& adj, int start) { - priority_queue<path, vector<path>, greater<path>> pq; - vector<ll> dist(sz(adj), INF); - vector<int> prev(sz(adj), -1); - dist[start] = 0; pq.emplace(0, start); +auto dijkstra(vector<vector<pair<int, Dist>>> &adj, int start) { + priority_queue<pair<Dist, int>> pq; + vector<Dist> dist(ssize(adj), INF); + dist[start] = 0, pq.emplace(0, start); - while (!pq.empty()) { - auto [dv, v] = pq.top(); pq.pop(); - if (dv > dist[v]) continue; // WICHTIG! + while (!empty(pq)) { + auto [du, u] = pq.top(); + du = -du, pq.pop(); + if (du > dist[u]) continue; // WICHTIG! - for (auto [du, u] : adj[v]) { - ll newDist = dv + du; - if (newDist < dist[u]) { - dist[u] = newDist; - prev[u] = v; - pq.emplace(dist[u], u); - }}} - return dist; //return prev; + for (auto [v, d]: adj[u]) { + Dist dv = du + d; + if (dv < dist[v]) dist[v] = dv, pq.emplace(-dv, v); + }} + return dist; } diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp index 2e58a2d..c8c34a8 100644 --- a/content/graph/dinic.cpp +++ b/content/graph/dinic.cpp @@ -8,12 +8,12 @@ int s, t; vector<int> pt, dist; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); } bool bfs() { - dist.assign(sz(adj), -1); + dist.assign(ssize(adj), -1); dist[s] = 0; queue<int> q({s}); while (!q.empty() && dist[t] < 0) { @@ -28,7 +28,7 @@ bool bfs() { ll dfs(int v, ll flow = INF) { if (v == t || flow == 0) return flow; - for (; pt[v] < sz(adj[v]); pt[v]++) { + for (; pt[v] < ssize(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; ll cur = dfs(e.to, min(e.c - e.f, flow)); @@ -44,7 +44,7 @@ ll maxFlow(int source, int target) { s = source, t = target; ll flow = 0; while (bfs()) { - pt.assign(sz(adj), 0); + pt.assign(ssize(adj), 0); ll cur; do { cur = dfs(s); diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index 0974b78..0082c05 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -8,12 +8,12 @@ int s, t; vector<int> pt, dist; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); } bool bfs(ll lim) { - dist.assign(sz(adj), -1); + dist.assign(ssize(adj), -1); dist[s] = 0; queue<int> q({s}); while (!q.empty() && dist[t] < 0) { @@ -28,7 +28,7 @@ bool bfs(ll lim) { ll dfs(int v, ll flow) { if (v == t || flow == 0) return flow; - for (; pt[v] < sz(adj[v]); pt[v]++) { + for (; pt[v] < ssize(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; ll cur = dfs(e.to, min(e.c - e.f, flow)); @@ -45,7 +45,7 @@ ll maxFlow(int source, int target) { ll flow = 0; for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { - pt.assign(sz(adj), 0); + pt.assign(ssize(adj), 0); ll cur; do { cur = dfs(s, lim); diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index e81cebe..d45dac0 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -2,8 +2,8 @@ vector<vector<pair<int, int>>> adj; // gets destroyed! vector<int> cycle; void addEdge(int u, int v) { - adj[u].emplace_back(v, sz(adj[v])); - adj[v].emplace_back(u, sz(adj[u]) - 1); // remove for directed + adj[u].emplace_back(v, ssize(adj[v])); + adj[v].emplace_back(u, ssize(adj[u]) - 1); // remove for directed } void euler(int v) { diff --git a/content/graph/floydWarshall.cpp b/content/graph/floydWarshall.cpp index df096c2..1a1138d 100644 --- a/content/graph/floydWarshall.cpp +++ b/content/graph/floydWarshall.cpp @@ -2,16 +2,16 @@ vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten. vector<vector<int>> next; void floydWarshall() { - next.assign(sz(dist), vector<int>(sz(dist), -1)); - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { + next.assign(ssize(dist), vector<int>(ssize(dist), -1)); + for (int i = 0; i < ssize(dist); i++) { + for (int j = 0; j < ssize(dist); j++) { if (dist[i][j] < INF) { next[i][j] = j; }}} - for (int k = 0; k < sz(dist); k++) { - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { + for (int k = 0; k < ssize(dist); k++) { + for (int i = 0; i < ssize(dist); i++) { + for (int j = 0; j < ssize(dist); j++) { // only needed if dist can be negative if (dist[i][k] == INF || dist[k][j] == INF) continue; if (dist[i][j] > dist[i][k] + dist[k][j]) { diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 213c597..6e8e20b 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -1,12 +1,5 @@ \section{Graphen} -\begin{algorithm}{Kruskal} - \begin{methods}[ll] - berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ - \end{methods} - \sourcecode{graph/kruskal.cpp} -\end{algorithm} - \begin{algorithm}{Minimale Spannbäume} \paragraph{Schnitteigenschaft} Für jeden Schnitt $C$ im Graphen gilt: @@ -16,6 +9,12 @@ \paragraph{Kreiseigenschaft} Für jeden Kreis $K$ im Graphen gilt: Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. + + \subsection{\textsc{Kruskal}} + \begin{methods}[ll] + berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ + \end{methods} + \sourcecode{graph/kruskal.cpp} \end{algorithm} \begin{algorithm}{Heavy-Light Decomposition} @@ -28,7 +27,7 @@ \sourcecode{graph/hld.cpp} \end{algorithm} -\begin{algorithm}{Lowest Common Ancestor} +\begin{algorithm}[optional]{Lowest Common Ancestor} \begin{methods} \method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})} \method{getLCA}{findet LCA}{1} @@ -37,6 +36,17 @@ \sourcecode{graph/LCA_sparse.cpp} \end{algorithm} +\begin{algorithm}{Binary Lifting} + % https://codeforces.com/blog/entry/74847 + \begin{methods} + \method{Lift}{constructor}{\abs{V}} + \method{depth}{distance to root of vertex $v$}{1} + \method{lift}{vertex above $v$ at depth $d$}{\log(\abs{V})} + \method{lca}{lowest common ancestor of $u$ and $v$}{\log(\abs{V})} + \end{methods} + \sourcecode{graph/binary_lifting.cpp} +\end{algorithm} + \begin{algorithm}{Centroids} \begin{methods} \method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}} @@ -99,7 +109,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/connect.cpp} \end{algorithm} -\begin{algorithm}{Erd\H{o}s-Gallai} +\begin{algorithm}{\textsc{Erd\H{o}s-Gallai}} Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$ \begin{methods} \method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})} @@ -170,7 +180,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/virtualTree.cpp} \end{algorithm} -\begin{algorithm}{Maximum Cardinatlity Bipartite Matching} +\begin{algorithm}{Maximum Cardinality Bipartite Matching} \label{kuhn} \begin{methods} \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} @@ -178,7 +188,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \begin{itemize} \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen \end{itemize} - \sourcecode{graph/maxCarBiMatch.cpp} + \sourcecode{graph/kuhn.cpp} \begin{methods} \method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}} \end{methods} @@ -197,7 +207,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \subsection{Max-Flow} \optional{ -\subsubsection{Push Relabel} +\subsubsection{Push Relabel \opthint} \begin{methods} \method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} @@ -205,24 +215,23 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/pushRelabel.cpp} } +\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} +\begin{methods} + \method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}} + \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} +\end{methods} +\sourcecode{graph/dinicScaling.cpp} + \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} -\vfill\null \columnbreak -\subsubsection{Dinic's Algorithm mit Capacity Scaling} -\begin{methods} - \method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}} - \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} -\end{methods} -\sourcecode{graph/dinicScaling.cpp} - \optional{ -\subsubsection{Anwendungen} +\subsubsection{Anwendungen \opthint} \begin{itemize} \item \textbf{Maximum Edge Disjoint Paths}\newline Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. diff --git a/content/graph/havelHakimi.cpp b/content/graph/havelHakimi.cpp index ac4d67d..9f4c081 100644 --- a/content/graph/havelHakimi.cpp +++ b/content/graph/havelHakimi.cpp @@ -1,12 +1,12 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) { priority_queue<pair<int, int>> pq; - for (int i = 0; i < sz(deg); i++) { + for (int i = 0; i < ssize(deg); i++) { if (deg[i] > 0) pq.push({deg[i], i}); } - vector<vector<int>> adj(sz(deg)); + vector<vector<int>> adj(ssize(deg)); while (!pq.empty()) { auto [degV, v] = pq.top(); pq.pop(); - if (sz(pq) < degV) return {}; //impossible + if (ssize(pq) < degV) return {}; //impossible vector<pair<int, int>> todo(degV); for (auto& e : todo) e = pq.top(), pq.pop(); for (auto [degU, u] : todo) { diff --git a/content/graph/hld.cpp b/content/graph/hld.cpp index 65d3f5c..e365b13 100644 --- a/content/graph/hld.cpp +++ b/content/graph/hld.cpp @@ -21,7 +21,7 @@ void dfs_hld(int v = 0, int from = -1) { } void init(int root = 0) { - int n = sz(adj); + int n = ssize(adj); sz.assign(n, 1), nxt.assign(n, root), par.assign(n, -1); in.resize(n), out.resize(n); counter = 0; diff --git a/content/graph/hopcroftKarp.cpp b/content/graph/hopcroftKarp.cpp index c1f5d1c..d07bd3a 100644 --- a/content/graph/hopcroftKarp.cpp +++ b/content/graph/hopcroftKarp.cpp @@ -5,14 +5,14 @@ vector<int> pairs, dist, ptr; bool bfs(int l) { queue<int> q; for(int v = 0; v < l; v++) { - if (pairs[v] < 0) {dist[v] = 0; q.push(v);} + if (pairs[v] < 0) { dist[v] = 0; q.push(v); } else dist[v] = -1; } bool exist = false; while(!q.empty()) { int v = q.front(); q.pop(); for (int u : adj[v]) { - if (pairs[u] < 0) {exist = true; continue;} + if (pairs[u] < 0) { exist = true; continue; } if (dist[pairs[u]] < 0) { dist[pairs[u]] = dist[v] + 1; q.push(pairs[u]); @@ -21,7 +21,7 @@ bool bfs(int l) { } bool dfs(int v) { - for (; ptr[v] < sz(adj[v]); ptr[v]++) { + for (; ptr[v] < ssize(adj[v]); ptr[v]++) { int u = adj[v][ptr[v]]; if (pairs[u] < 0 || (dist[pairs[u]] > dist[v] && dfs(pairs[u]))) { @@ -33,7 +33,7 @@ bool dfs(int v) { int hopcroft_karp(int l) { // l = #Knoten links int ans = 0; - pairs.assign(sz(adj), -1); + pairs.assign(ssize(adj), -1); dist.resize(l); // Greedy Matching, optionale Beschleunigung. for (int v = 0; v < l; v++) for (int u : adj[v]) diff --git a/content/graph/kruskal.cpp b/content/graph/kruskal.cpp index 987d30b..d42800d 100644 --- a/content/graph/kruskal.cpp +++ b/content/graph/kruskal.cpp @@ -1,4 +1,4 @@ -sort(all(edges)); +ranges::sort(edges, less{}); vector<Edge> mst; ll cost = 0; for (Edge& e : edges) { diff --git a/content/graph/maxCarBiMatch.cpp b/content/graph/kuhn.cpp index e928387..688c846 100644 --- a/content/graph/maxCarBiMatch.cpp +++ b/content/graph/kuhn.cpp @@ -12,7 +12,7 @@ bool dfs(int v) { } int kuhn(int l) { // l = #Knoten links. - pairs.assign(sz(adj), -1); + pairs.assign(ssize(adj), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. for (int v = 0; v < l; v++) for (int u : adj[v]) diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp index dcaea8c..3619d7c 100644 --- a/content/graph/matching.cpp +++ b/content/graph/matching.cpp @@ -3,19 +3,19 @@ vector<vector<ll>> adj, mat; int max_matching() { int ans = 0; - mat.assign(sz(adj), {}); + mat.assign(ssize(adj), {}); for (int _ = 0; _ < I; _++) { - for (int v = 0; v < sz(adj); v++) { - mat[v].assign(sz(adj), 0); + for (int v = 0; v < ssize(adj); v++) { + mat[v].assign(ssize(adj), 0); for (int u : adj[v]) { if (u < v) { mat[v][u] = rand() % (MOD - 1) + 1; mat[u][v] = MOD - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ + gauss(ssize(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { - if (*max_element(all(row)) != 0) rank++; + if (*ranges::max_element(row) != 0) rank++; } ans = max(ans, rank / 2); } diff --git a/content/graph/maxWeightBipartiteMatching.cpp b/content/graph/maxWeightBipartiteMatching.cpp index a2b0a80..b6f6ddf 100644 --- a/content/graph/maxWeightBipartiteMatching.cpp +++ b/content/graph/maxWeightBipartiteMatching.cpp @@ -45,6 +45,6 @@ double match(int l, int r) { yx[y] = aug[y]; swap(y, xy[aug[y]]); }} - return accumulate(all(lx), 0.0) + - accumulate(all(ly), 0.0); // Wert des Matchings + return accumulate(begin(lx), end(lx), 0.0) + + accumulate(begin(ly), end(ly), 0.0); // Wert des Matchings } diff --git a/content/graph/minCostMaxFlow.cpp b/content/graph/minCostMaxFlow.cpp index 14a222c..fde95f3 100644 --- a/content/graph/minCostMaxFlow.cpp +++ b/content/graph/minCostMaxFlow.cpp @@ -15,16 +15,16 @@ struct MinCostFlow { adj(n), s(source), t(target) {}; void addEdge(int u, int v, ll c, ll cost) { - adj[u].push_back(sz(edges)); + adj[u].push_back(ssize(edges)); edges.push_back({v, c, cost}); - adj[v].push_back(sz(edges)); + adj[v].push_back(ssize(edges)); edges.push_back({u, 0, -cost}); } bool SPFA() { - pref.assign(sz(adj), -1); - dist.assign(sz(adj), INF); - vector<bool> inqueue(sz(adj)); + pref.assign(ssize(adj), -1); + dist.assign(ssize(adj), INF); + vector<bool> inqueue(ssize(adj)); queue<int> queue; dist[s] = 0; queue.push(s); @@ -59,7 +59,7 @@ struct MinCostFlow { }} void mincostflow() { - con.assign(sz(adj), 0); + con.assign(ssize(adj), 0); maxflow = mincost = 0; while (SPFA()) extend(); } diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp index ec36026..c569df2 100644 --- a/content/graph/pushRelabel.cpp +++ b/content/graph/pushRelabel.cpp @@ -9,8 +9,8 @@ vector<ll> ec; vector<int> cur, H; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u])-1, 0, 0}); } void addFlow(Edge& e, ll f) { @@ -23,7 +23,7 @@ void addFlow(Edge& e, ll f) { } ll maxFlow(int s, int t) { - int n = sz(adj); + int n = ssize(adj); hs.assign(2*n, {}); ec.assign(n, 0); cur.assign(n, 0); @@ -38,9 +38,9 @@ ll maxFlow(int s, int t) { int v = hs[hi].back(); hs[hi].pop_back(); while (ec[v] > 0) { - if (cur[v] == sz(adj[v])) { + if (cur[v] == ssize(adj[v])) { H[v] = 2*n; - for (int i = 0; i < sz(adj[v]); i++) { + for (int i = 0; i < ssize(adj[v]); i++) { Edge& e = adj[v][i]; if (e.c - e.f > 0 && H[v] > H[e.to] + 1) { diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 379c839..5a9c9d1 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -26,11 +26,11 @@ struct Reroot { pref.push_back(takeChild(v, u, w, dp[u])); } auto suf = pref; - partial_sum(all(pref), pref.begin(), comb); + partial_sum(begin(pref), end(pref), begin(pref), comb); exclusive_scan(suf.rbegin(), suf.rend(), suf.rbegin(), E, comb); - for (int i = 0; i < sz(adj[v]); i++) { + for (int i = 0; i < ssize(adj[v]); i++) { auto [u, w] = adj[v][i]; if (u == from) continue; dp[v] = fin(v, comb(pref[i], suf[i + 1])); @@ -40,7 +40,7 @@ struct Reroot { } auto solve() { - dp.assign(sz(adj), E); + dp.assign(ssize(adj), E); dfs0(0); dfs1(0); return dp; diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index 32f1099..6887712 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -23,11 +23,11 @@ void visit(int v) { }}} void scc() { - inStack.assign(sz(adj), false); - low.assign(sz(adj), -1); - idx.assign(sz(adj), -1); + inStack.assign(ssize(adj), false); + low.assign(ssize(adj), -1); + idx.assign(ssize(adj), -1); counter = sccCounter = 0; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 97e667a..a122488 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -7,7 +7,7 @@ vector<vector<Edge>> adj, tmp; vector<bool> erased; void merge(int u, int v) { - tmp[u].insert(tmp[u].end(), all(tmp[v])); + tmp[u].insert(end(tmp[u]), begin(tmp[v]), end(tmp[v])); tmp[v].clear(); erased[v] = true; for (auto& vec : tmp) { @@ -19,33 +19,33 @@ void merge(int u, int v) { ll stoer_wagner() { ll res = INF; tmp = adj; - erased.assign(sz(tmp), false); - for (int i = 1; i < sz(tmp); i++) { + erased.assign(ssize(tmp), false); + for (int i = 1; i < ssize(tmp); i++) { int s = 0; while (erased[s]) s++; priority_queue<pair<ll, int>> pq; pq.push({0, s}); - vector<ll> con(sz(tmp)); + vector<ll> con(ssize(tmp)); ll cur = 0; vector<pair<ll, int>> state; while (!pq.empty()) { int c = pq.top().second; pq.pop(); - if (con[c] < 0) continue; //already seen + if (con[c] < 0) continue; // already seen con[c] = -1; for (auto e : tmp[c]) { - if (con[e.to] >= 0) {//add edge to cut + if (con[e.to] >= 0) { // add edge to cut con[e.to] += e.cap; pq.push({con[e.to], e.to}); cur += e.cap; - } else if (e.to != c) {//remove edge from cut + } else if (e.to != c) { // remove edge from cut cur -= e.cap; }} state.push_back({cur, c}); } int t = state.back().second; state.pop_back(); - if (state.empty()) return 0; //graph is not connected?! + if (state.empty()) return 0; // graph is not connected?! merge(state.back().second, t); res = min(res, state.back().first); } diff --git a/content/graph/treeIsomorphism.cpp b/content/graph/treeIsomorphism.cpp index 355fefb..8c2ca21 100644 --- a/content/graph/treeIsomorphism.cpp +++ b/content/graph/treeIsomorphism.cpp @@ -7,9 +7,9 @@ int treeLabel(int v, int from = -1) { if (u == from) continue; children.push_back(treeLabel(u, v)); } - sort(all(children)); + ranges::sort(children); if (known.find(children) == known.end()) { - known[children] = sz(known); + known[children] = ssize(known); } return known[children]; } diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 6233b27..81ba001 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -2,14 +2,14 @@ vector<int> in, out; void virtualTree(vector<int> ind) { // indices of used nodes - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - for (int i = 1, n = sz(ind); i < n; i++) { + ranges::sort(ind, {}, [&](int x) { return in[x]; }); + for (int i = 1, n = ssize(ind); i < n; i++) { ind.push_back(lca(ind[i - 1], ind[i])); } - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - ind.erase(unique(all(ind)), ind.end()); + ranges::sort(ind, {}, [&](int x) { return in[x]; }); + ind.erase(begin(ranges::unique(ind)), end(ind)); - int n = sz(ind); + int n = ssize(ind); vector<vector<int>> tree(n); vector<int> st = {0}; for (int i = 1; i < n; i++) { |