From 630a5bdf06d59b8340fb4bfc0e692cbcf094026a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Thu, 10 Jul 2025 17:40:18 +0200 Subject: run with sanitizer --- content/graph/bitonicTSP.cpp | 2 +- content/graph/matching.cpp | 8 ++++---- 2 files changed, 5 insertions(+), 5 deletions(-) (limited to 'content/graph') diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index eee5082..f025bca 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -1,6 +1,6 @@ vector> dist; // Initialisiere mit Entfernungen zwischen Punkten. -auto bitonicTSP() { +auto bitonicTSP() { // n >= 2! vector dp(sz(dist), HUGE_VAL); vector pre(sz(dist)); // nur für Tour dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0; diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp index dcaea8c..1e450c0 100644 --- a/content/graph/matching.cpp +++ b/content/graph/matching.cpp @@ -1,4 +1,4 @@ -constexpr int MOD=1'000'000'007, I=10; +constexpr int mod=1'000'000'007, I=10; vector> adj, mat; int max_matching() { @@ -9,10 +9,10 @@ int max_matching() { mat[v].assign(sz(adj), 0); for (int u : adj[v]) { if (u < v) { - mat[v][u] = rand() % (MOD - 1) + 1; - mat[u][v] = MOD - mat[v][u]; + mat[v][u] = rand() % (mod - 1) + 1; + mat[u][v] = mod - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ + gauss(sz(mat), sz(mat[0])); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { if (*max_element(all(row)) != 0) rank++; -- cgit v1.2.3 From 919ec01b63a9e40c2f424220fbc8551a8e9f25f3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 9 Aug 2025 10:03:38 +0200 Subject: shortened code --- content/graph/bronKerbosch.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content/graph') diff --git a/content/graph/bronKerbosch.cpp b/content/graph/bronKerbosch.cpp index 0cfcc5f..9f7d8c5 100644 --- a/content/graph/bronKerbosch.cpp +++ b/content/graph/bronKerbosch.cpp @@ -9,7 +9,7 @@ void bronKerboschRec(bits R, bits P, bits X) { if (P.none() && X.none()) { cliques.push_back(R); } else { - int q = min(P._Find_first(), X._Find_first()); + int q = (P | X)._Find_first(); bits cands = P & ~adj[q]; for (int i = 0; i < sz(adj); i++) if (cands[i]) { R[i] = 1; -- cgit v1.2.3 From 1de6b74fab25d95e2802c97b4435f74266d4477d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 22 Sep 2025 17:27:12 +0200 Subject: small changes --- content/datastructures/unionFind.cpp | 2 +- content/graph/graph.tex | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'content/graph') diff --git a/content/datastructures/unionFind.cpp b/content/datastructures/unionFind.cpp index dd5a569..1ee5178 100644 --- a/content/datastructures/unionFind.cpp +++ b/content/datastructures/unionFind.cpp @@ -21,6 +21,6 @@ void unionSets(int a, int b) { // Diese Funktion aufrufen. if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); } -int size(int a) { +int size(int a) { // optional return -unions[findSet(a)]; } diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 5335967..7389ce6 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -106,7 +106,7 @@ \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} \method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3} \begin{itemize} - \item \code{dist[i][i] = 0, dist[i][j] = edge\{j, j\}.weight} oder \code{INF} + \item \code{dist[i][i] = 0, dist[i][j] = edge\{i, j\}.weight} oder \code{INF} \item \code{i} liegt auf einem negativen Kreis $\Leftrightarrow$ \code{dist[i][i] < 0}. \end{itemize} \sourcecode{graph/floydWarshall.cpp} @@ -128,7 +128,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \begin{algorithm}{Dynamic Connectivity} \begin{methods} \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} - \method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)} + \method{addEdge}{fügt Kante ein,\code{id}=delete Zeitpunkt}{\log(n)} \method{eraseEdge}{entfernt Kante \code{id}}{\log(n)} \end{methods} \sourcecode{graph/connect.cpp} -- cgit v1.2.3