summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
Diffstat (limited to 'graph')
-rw-r--r--graph/LCA.cpp24
-rw-r--r--graph/LCA_sparse.cpp6
-rw-r--r--graph/binary_lifting.cpp28
-rw-r--r--graph/cycleCounting.cpp4
-rw-r--r--graph/graph.tex51
-rw-r--r--graph/test/LCA_sparse.cpp63
-rw-r--r--graph/test/binary_lifting.cpp67
-rw-r--r--graph/test/util.cpp60
8 files changed, 253 insertions, 50 deletions
diff --git a/graph/LCA.cpp b/graph/LCA.cpp
deleted file mode 100644
index 7debf8f..0000000
--- a/graph/LCA.cpp
+++ /dev/null
@@ -1,24 +0,0 @@
-vector<vector<int>> adj();
-vector<int> visited();
-vector<int> first();
-vector<int> depth();
-
-void initLCA(int gi, int d, int& c) {
- visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
- for(int gn : adj[gi]) {
- initLCA(gn, d+1, c);
- visited[c] = gi, depth[c] = d, c++;
-}}
-
-int getLCA(int a, int b) {
- return visited[query(min(first[a], first[b]), max(first[a], first[b]))];
-}
-
-void exampleUse() {
- int c = 0;
- visited = vector<int>(2*sz(adj));
- first = vector<int>(sz(adj), 2*sz(adj));
- depth = vector<int>(2*sz(adj));
- initLCA(0, 0, c);
- init(depth);
-}
diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp
index 649e697..3e87cde 100644
--- a/graph/LCA_sparse.cpp
+++ b/graph/LCA_sparse.cpp
@@ -10,16 +10,16 @@ struct LCA {
first.assign(sz(adj), 2 * sz(adj));
idx = 0;
dfs(adj, root);
- st.init(&depth);
+ st.init(depth);
}
- void dfs(vector<vector<int>>& adj, int v, ll d=0, int p=-1) {
+ void dfs(vector<vector<int>>& adj, int v, ll d=0) {
visited[idx] = v, depth[idx] = d;
first[v] = min(idx, first[v]), idx++;
for (int u : adj[v]) {
if (first[u] == 2 * sz(adj)) {
- dfs(adj, u, d + 1, v);
+ dfs(adj, u, d + 1);
visited[idx] = v, depth[idx] = d, idx++;
}}}
diff --git a/graph/binary_lifting.cpp b/graph/binary_lifting.cpp
new file mode 100644
index 0000000..0b8c218
--- /dev/null
+++ b/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) {
+ function<void(int,int,int)> dfs = [&](int u, int p, int d) {
+ 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) dfs(v, u, d+1);
+ };
+ 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/graph/cycleCounting.cpp b/graph/cycleCounting.cpp
index bd7a219..00ecc3a 100644
--- a/graph/cycleCounting.cpp
+++ b/graph/cycleCounting.cpp
@@ -1,12 +1,12 @@
constexpr int maxEdges = 128;
using cycle = bitset<maxEdges>;
-struct cylces {
+struct cycles {
vector<vector<pair<int, int>>> adj;
vector<bool> seen;
vector<cycle> paths, base;
vector<pair<int, int>> edges;
- cylces(int n) : adj(n), seen(n), paths(n) {}
+ cycles(int n) : adj(n), seen(n), paths(n) {}
void addEdge(int u, int v) {
adj[u].push_back({v, sz(edges)});
diff --git a/graph/graph.tex b/graph/graph.tex
index 9232090..9a0dc24 100644
--- a/graph/graph.tex
+++ b/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})}
@@ -169,7 +179,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
\sourcecode{graph/virtualTree.cpp}
\end{algorithm}
-\begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
+\begin{algorithm}{Maximum Cardinality Bipartite Matching}
\label{kuhn}
\begin{methods}
\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
@@ -195,7 +205,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
\subsection{Max-Flow}
\optional{
-\subsubsection{Capacity Scaling}
+\subsubsection{Capacity Scaling \opthint}
\begin{methods}
\method{maxFlow}{gut bei dünn besetzten Graphen.}{\abs{E}^2\*\log(C)}
\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
@@ -204,7 +214,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
}
\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}
@@ -212,24 +222,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}
-
-\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}
-\vfill\null
\columnbreak
\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/graph/test/LCA_sparse.cpp b/graph/test/LCA_sparse.cpp
new file mode 100644
index 0000000..c8b0017
--- /dev/null
+++ b/graph/test/LCA_sparse.cpp
@@ -0,0 +1,63 @@
+#include "util.cpp"
+#define all(X) begin(X), end(X)
+#define sz ssize
+#include "../../datastructures/sparseTable.cpp"
+#include "../LCA_sparse.cpp"
+
+void test(vector<vector<int>> &adj, int root) {
+ int n = adj.size();
+
+ vector<int> parent(n);
+ function<void(int,int)> dfs = [&](int u, int p) {
+ parent[u] = p;
+ for (int v: adj[u]) if (v != p) dfs(v, u);
+ };
+ dfs(root, -1);
+
+ function<bool(int, int)> is_ancestor = [&](int u, int v) {
+ while (v != -1 && u != v) v = parent[v];
+ return u == v;
+ };
+ function<int(int)> depth = [&](int v) {
+ int r = 0;
+ while ((v = parent[v]) != -1) r++;
+ return r;
+ };
+
+ LCA lca;
+ lca.init(adj, root);
+ for (int i = 0; i < n; i++) assert(lca.getDepth(i) == depth(i));
+ for (int i = 0; i < 1000; i++) {
+ int u = util::randint(n);
+ int v = util::randint(n);
+ int l = lca.getLCA(u, v);
+ assert(is_ancestor(l, u));
+ assert(is_ancestor(l, v));
+ for (int p = parent[l]; int c: adj[l]) {
+ if (c == p) continue;
+ assert(!is_ancestor(c, u) || !is_ancestor(c, v));
+ }
+ }
+}
+
+int main() {
+ {
+ // Single vertex
+ vector<vector<int>> adj(1);
+ test(adj, 0);
+ }
+ {
+ // Path
+ vector<vector<int>> adj = util::path(100);
+ int left = 0, mid = 40, right = 99;
+ util::shuffle_graph(adj, left, mid, right);
+ test(adj, left);
+ test(adj, mid);
+ test(adj, right);
+ }
+ {
+ // Random
+ vector<vector<int>> adj = util::random_tree(1000);
+ test(adj, 0);
+ }
+}
diff --git a/graph/test/binary_lifting.cpp b/graph/test/binary_lifting.cpp
new file mode 100644
index 0000000..05b903a
--- /dev/null
+++ b/graph/test/binary_lifting.cpp
@@ -0,0 +1,67 @@
+#include "util.cpp"
+#include "../binary_lifting.cpp"
+
+void test(vector<vector<int>> &adj, int root) {
+ int n = adj.size();
+
+ vector<int> parent(n);
+ function<void(int,int)> dfs = [&](int u, int p) {
+ parent[u] = p;
+ for (int v: adj[u]) if (v != p) dfs(v, u);
+ };
+ dfs(root, -1);
+
+ function<bool(int, int)> is_ancestor = [&](int u, int v) {
+ while (v != -1 && u != v) v = parent[v];
+ return u == v;
+ };
+ function<int(int)> depth = [&](int v) {
+ int r = 0;
+ while ((v = parent[v]) != -1) r++;
+ return r;
+ };
+
+ Lift lift(adj, root);
+ for (int i = 0; i < n; i++) assert(lift.depth(i) == depth(i));
+ for (int i = 0; i < 1000; i++) {
+ int v = util::randint(n);
+ int d = util::randint(n);
+ int u = lift.lift(v, d);
+ assert(is_ancestor(u, v));
+ if (d <= depth(v)) assert(depth(u) == d);
+ else assert(u == v);
+ }
+ for (int i = 0; i < 1000; i++) {
+ int u = util::randint(n);
+ int v = util::randint(n);
+ int lca = lift.lca(u, v);
+ assert(is_ancestor(lca, u));
+ assert(is_ancestor(lca, v));
+ for (int p = parent[lca]; int c: adj[lca]) {
+ if (c == p) continue;
+ assert(!is_ancestor(c, u) || !is_ancestor(c, v));
+ }
+ }
+}
+
+int main() {
+ {
+ // Single vertex
+ vector<vector<int>> adj(1);
+ test(adj, 0);
+ }
+ {
+ // Path
+ vector<vector<int>> adj = util::path(100);
+ int left = 0, mid = 40, right = 99;
+ util::shuffle_graph(adj, left, mid, right);
+ test(adj, left);
+ test(adj, mid);
+ test(adj, right);
+ }
+ {
+ // Random
+ vector<vector<int>> adj = util::random_tree(1000);
+ test(adj, 0);
+ }
+}
diff --git a/graph/test/util.cpp b/graph/test/util.cpp
new file mode 100644
index 0000000..8c14b5c
--- /dev/null
+++ b/graph/test/util.cpp
@@ -0,0 +1,60 @@
+
+namespace util {
+
+void shuffle_adj_lists(vector<vector<int>> &adj) {
+ for (auto &a: adj) ranges::shuffle(a, rd);
+}
+
+vector<vector<int>> random_tree(int n) {
+ vector<vector<int>> adj(n);
+
+ vector<vector<int>> components(n);
+ for (int i = 0; i < n; i++) components[i].push_back(i);
+ while (components.size() > 1) {
+ int c1 = randint(components.size());
+ int c2 = randint(components.size()-1);
+ c2 += (c2 >= c1);
+
+ int v1 = components[c1][randint(components[c1].size())];
+ int v2 = components[c2][randint(components[c2].size())];
+
+ adj[v1].push_back(v2);
+ adj[v2].push_back(v1);
+
+ if (components[c1].size() < components[c2].size()) swap(c1, c2);
+ for (int v: components[c2]) components[c1].push_back(v);
+ swap(components[c2], components.back());
+ components.pop_back();
+ }
+
+ shuffle_adj_lists(adj);
+ return adj;
+}
+
+vector<vector<int>> path(int n) {
+ vector<vector<int>> adj(n);
+ for (int i = 1; i < n; i++) {
+ adj[i-1].push_back(i);
+ adj[i].push_back(i-1);
+ }
+ return adj;
+}
+
+template<typename... Ts>
+void shuffle_graph(vector<vector<int>> &adj, Ts &...vertex) {
+ int n = adj.size();
+ vector<int> perm(n);
+ iota(perm.begin(), perm.end(), 0);
+ ranges::shuffle(perm, rd);
+
+ vector<vector<int>> new_adj(n);
+ for (int i = 0; i < n; i++) {
+ auto &a = new_adj[perm[i]] = move(adj[i]);
+ for (int &v: a) v = perm[v];
+ }
+ adj = move(new_adj);
+ shuffle_adj_lists(adj);
+ ((vertex = perm[vertex]), ...);
+}
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 18:50:13 +0000