diff options
| -rw-r--r-- | graph/binary_lifting.cpp | 28 | ||||
| -rw-r--r-- | graph/graph.tex | 12 |
2 files changed, 39 insertions, 1 deletions
diff --git a/graph/binary_lifting.cpp b/graph/binary_lifting.cpp new file mode 100644 index 0000000..9e0dfc3 --- /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) { + if (jmp[u] == jmp[v]) u = par[u], v = par[v]; + else u = jmp[u], v = jmp[v]; + } + return u; + } +}; diff --git a/graph/graph.tex b/graph/graph.tex index 6fbdb74..b251278 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -15,7 +15,7 @@ \end{itemize} \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} @@ -24,6 +24,16 @@ \sourcecode{graph/LCA_sparse.cpp} \end{algorithm} +\begin{algorithm}{Binary Lifting} + \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}} |