diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/LCA_sparse.cpp | 2 | ||||
| -rw-r--r-- | graph/cycleCounting.cpp | 2 | ||||
| -rw-r--r-- | graph/graph.tex | 6 | ||||
| -rw-r--r-- | graph/matching.cpp | 2 |
4 files changed, 6 insertions, 6 deletions
diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp index 06b294f..3e87cde 100644 --- a/graph/LCA_sparse.cpp +++ b/graph/LCA_sparse.cpp @@ -2,7 +2,7 @@ struct LCA { vector<ll> depth; vector<int> visited, first; int idx; - SparseTable st; //sparse table von oben + SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector<vector<int>>& adj, int root) { depth.assign(2 * sz(adj), 0); diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp index 0df464b..00ecc3a 100644 --- a/graph/cycleCounting.cpp +++ b/graph/cycleCounting.cpp @@ -39,7 +39,7 @@ struct cycles { //cycle must be constrcuted from base bool isCycle(cycle cur) { if (cur.none()) return false; - init(sz(adj)); // union find + init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ for (int i = 0; i < sz(edges); i++) { if (cur[i]) { cur[i] = false; diff --git a/graph/graph.tex b/graph/graph.tex index c6b2248..9a0dc24 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -98,7 +98,7 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \min\{a_{ik} \cdot b_{k\smash{j}}\}$ -Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$ +Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} \cdot b_{k\smash{j}}$ \begin{algorithm}{Dynamic Connectivity} \begin{methods} @@ -185,7 +185,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} \end{methods} \begin{itemize} - \item die ersten [0..n) Knoten in \code{adj} sind die linke Seite des Graphen + \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen \end{itemize} \sourcecode{graph/maxCarBiMatch.cpp} \begin{methods} @@ -265,7 +265,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} -\vfill* +\vfill\null \columnbreak diff --git a/graph/matching.cpp b/graph/matching.cpp index f059351..2513604 100644 --- a/graph/matching.cpp +++ b/graph/matching.cpp @@ -12,7 +12,7 @@ int max_matching() { mat[v][u] = rand() % (MOD - 1) + 1; mat[u][v] = MOD - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS unten + gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { if (*min_element(all(row)) != 0) rank++; |