From a9d0fb392d56315139a0d2683217bc7a54bd7cce Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 21 Apr 2025 13:33:59 +0200 Subject: merge --- content/geometry/polygon.cpp | 2 +- content/graph/dinicScaling.cpp | 1 + content/graph/graph.tex | 1 + content/graph/scc.cpp | 20 ++++++------------ content/other/other.tex | 4 ++-- tcr.pdf | Bin 703380 -> 698354 bytes test/graph/scc.cpp | 47 ++++++++++++++++------------------------- 7 files changed, 30 insertions(+), 45 deletions(-) diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 1332a4a..11ae2f7 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -23,7 +23,7 @@ ll windingNumber(pt p, const vector& poly) { return res; } -// check if point is inside polygon (any polygon) +// check if p is inside poly (any polygon poly[0] == poly.back()) bool inside(pt p, const vector& poly) { bool in = false; for (int i = 0; i + 1 < sz(poly); i++) { diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index 0974b78..b0828d0 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -43,6 +43,7 @@ ll dfs(int v, ll flow) { ll maxFlow(int source, int target) { s = source, t = target; ll flow = 0; + // set lim = 1 and use dfs(s, INF) to disable scaling for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { pt.assign(sz(adj), 0); diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 213c597..eb12cdb 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -111,6 +111,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \begin{methods} \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} \end{methods} + \textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge! \sourcecode{graph/scc.cpp} \end{algorithm} diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index 32f1099..a6af7d6 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -1,33 +1,27 @@ vector> adj; -int counter, sccCounter; -vector inStack; +int sccCounter; vector low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { - int old = low[v] = counter++; + int old = low[v] = sz(s); s.push_back(v); - inStack[v] = true; for (auto u : adj[v]) { if (low[u] < 0) visit(u); - if (inStack[u]) low[v] = min(low[v], low[u]); + if (idx[u] < 0) low[v] = min(low[v], low[u]); } if (old == low[v]) { + for (int i = old; i < sz(s); i++) idx[s[i]] = sccCounter; sccCounter++; - for (int u = -1; u != v;) { - u = s.back(); - s.pop_back(); - inStack[u] = false; - idx[u] = sccCounter - 1; -}}} + s.resize(old); +}} void scc() { - inStack.assign(sz(adj), false); low.assign(sz(adj), -1); idx.assign(sz(adj), -1); - counter = sccCounter = 0; + sccCounter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/content/other/other.tex b/content/other/other.tex index 191a6da..a38f6da 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -147,7 +147,7 @@ Im Residualgraphen: \begin{itemize} \item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder} - \item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{erreichbar} sind. + \item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{s} erreichbar sind. \end{itemize} \item \textbf{Allgemeiner Graph:} @@ -156,7 +156,7 @@ \item \textbf{Bipartiter Graph:} Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching. - Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, makiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die makierten Knoten aus $B$ und die unmakierten Knoten aus $A$. + Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$. \item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:} Minimiere Matchinggewicht. diff --git a/tcr.pdf b/tcr.pdf index 76c898a..6b38da9 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index 9ab7051..cf4efc7 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -1,6 +1,5 @@ #include "../util.h" #include -#include void stress_test() { ll queries = 0; @@ -16,37 +15,27 @@ void stress_test() { }); scc(); - init(n); - vector seen(n); - int tmpCounter = 0; - auto reach = [&](int a, int b) { - tmpCounter++; - seen[a] = tmpCounter; - vector todo = {a}; - while (seen[b] != tmpCounter && !todo.empty()) { - a = todo.back(); - todo.pop_back(); - g.forOut(a, [&](int /**/, int x){ - if (seen[x] != tmpCounter) { - seen[x] = tmpCounter; - todo.push_back(x); - } + auto reach = [&](int a) -> vector { + vector seen(n); + auto dfs = [&](auto &&self, int u) -> void { + if (seen[u]) return; + seen[u] = true; + g.forOut(u, [&](int, int v) { + self(self, v); }); - } - return seen[b] == tmpCounter; + }; + dfs(dfs, a); + return seen; }; - for (int a = 0; a < n; a++) { - for (int b = 0; b < a; b++) { - if (findSet(a) == findSet(b)) continue; - if (reach(a, b) && reach(b, a)) unionSets(a, b); - } - } for (int a = 0; a < n; a++) { - for (int b = 0; b <= a; b++) { - bool got = idx[a] == idx[b]; - bool expected = findSet(a) == findSet(b); - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + vector reacha = reach(a); + for (int b = 0; b < n; b++) { + if (idx[a] == idx[b]) { + if (!reacha[b]) cerr << a << " and " << b << " should be in different SCCs" << FAIL; + } else if (idx[a] < idx[b]) { + if (reacha[b]) cerr << a << " should come before " << b << " in topological order" << FAIL; + } } } queries += n; @@ -66,7 +55,7 @@ void performance_test() { }); t.start(); - scc(); + scc(); t.stop(); hash_t hash = 0; for (int x : idx) hash += x; -- cgit v1.2.3 From a5b6a77772a705cccfd25a108a966cc5070d63a3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 21 Apr 2025 13:28:59 +0200 Subject: moved stuff --- content/graph/2sat.cpp | 4 +- content/graph/bellmannFord.cpp | 1 - content/graph/graph.tex | 208 ++++++++++++++++++++++------------------- tcr.pdf | Bin 698354 -> 698689 bytes 4 files changed, 112 insertions(+), 101 deletions(-) diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp index 75e54e6..3e0811f 100644 --- a/content/graph/2sat.cpp +++ b/content/graph/2sat.cpp @@ -1,11 +1,9 @@ +constexpr int var(int i) {return i << 1;} // use this! struct sat2 { int n; // + scc variablen vector sol; - sat2(int vars) : n(vars*2), adj(n) {} - 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); diff --git a/content/graph/bellmannFord.cpp b/content/graph/bellmannFord.cpp index 09ea1aa..cadcde7 100644 --- a/content/graph/bellmannFord.cpp +++ b/content/graph/bellmannFord.cpp @@ -9,7 +9,6 @@ auto bellmannFord(int n, vector& edges, int start) { dist[e.to] = dist[e.from] + e.cost; prev[e.to] = e.from; }}} - for (edge& e : edges) { if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to]) { diff --git a/content/graph/graph.tex b/content/graph/graph.tex index eb12cdb..5335967 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -66,15 +66,42 @@ \sourcecode{graph/treeIsomorphism.cpp} \end{algorithm} -\subsection{Kürzeste Wege} +\begin{algorithm}{DFS} + \input{graph/dfs} +\end{algorithm} -\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} -\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}} -\sourcecode{graph/bellmannFord.cpp} +\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} + \begin{methods} + \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} + \end{methods} + \textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge! + \sourcecode{graph/scc.cpp} +\end{algorithm} -\subsubsection{Algorithmus von \textsc{Dijkstra}} -\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})} -\sourcecode{graph/dijkstra.cpp} +\begin{algorithm}{2-SAT} + \sourcecode{graph/2sat.cpp} +\end{algorithm} + +\begin{algorithm}{Artikulationspunkte, Brücken und BCC} + \begin{methods} + \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}} + \end{methods} + \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. + \sourcecode{graph/articulationPoints.cpp} +\end{algorithm} + +\begin{algorithm}{Cycle Counting} + \begin{methods} + \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}} + \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}} + \end{methods} + \begin{itemize} + \item jeder Zyklus ist das xor von einträgen in \code{base}. + \end{itemize} + \sourcecode{graph/cycleCounting.cpp} +\end{algorithm} + +\subsection{Kürzeste Wege} \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} \method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3} @@ -90,6 +117,14 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die 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}}$ +\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}} +\sourcecode{graph/bellmannFord.cpp} + +\subsubsection{Algorithmus von \textsc{Dijkstra}} +\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})} +\sourcecode{graph/dijkstra.cpp} + \begin{algorithm}{Dynamic Connectivity} \begin{methods} \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} @@ -99,38 +134,13 @@ 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} - 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})} - \end{methods} - \sourcecode{graph/havelHakimi.cpp} -\end{algorithm} -\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} - \begin{methods} - \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} - \end{methods} - \textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge! - \sourcecode{graph/scc.cpp} -\end{algorithm} -\begin{algorithm}{DFS} - \input{graph/dfs} -\end{algorithm} -\begin{algorithm}{Artikulationspunkte, Brücken und BCC} - \begin{methods} - \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}} - \end{methods} - \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. - \sourcecode{graph/articulationPoints.cpp} -\end{algorithm} -\vfill\null\columnbreak -\begin{algorithm}{2-SAT} - \sourcecode{graph/2sat.cpp} -\end{algorithm} + + + \begin{algorithm}{Maximal Cliques} \begin{methods} @@ -140,17 +150,35 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\begin{algorithm}{Cycle Counting} +\begin{algorithm}{Maximum Cardinatlity Bipartite Matching} + \label{kuhn} \begin{methods} - \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}} - \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}} + \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} \end{methods} \begin{itemize} - \item jeder Zyklus ist das xor von einträgen in \code{base}. + \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen \end{itemize} - \sourcecode{graph/cycleCounting.cpp} + \sourcecode{graph/maxCarBiMatch.cpp} + \columnbreak + \begin{methods} + \method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}} + \end{methods} + \sourcecode{graph/hopcroftKarp.cpp} +\end{algorithm} + +\vfill\null +\columnbreak + +\begin{algorithm}{Maximum Weight Bipartite Matching} + \begin{methods} + \method{match}{berechnet Matching}{\abs{V}^3} + \end{methods} + \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} +\vfill\null +\columnbreak + \begin{algorithm}{Wert des maximalen Matchings} Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$ \sourcecode{graph/matching.cpp} @@ -163,28 +191,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/blossom.cpp} \end{algorithm} -\begin{algorithm}{Rerooting Template} - \sourcecode{graph/reroot.cpp} -\end{algorithm} - -\begin{algorithm}{Virtual Trees} - \sourcecode{graph/virtualTree.cpp} -\end{algorithm} - -\begin{algorithm}{Maximum Cardinatlity Bipartite Matching} - \label{kuhn} - \begin{methods} - \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} - \end{methods} - \begin{itemize} - \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen - \end{itemize} - \sourcecode{graph/maxCarBiMatch.cpp} - \begin{methods} - \method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}} - \end{methods} - \sourcecode{graph/hopcroftKarp.cpp} -\end{algorithm} +\vfill\null +\columnbreak \begin{algorithm}{Global Mincut} \begin{methods} @@ -195,15 +203,31 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/stoerWagner.cpp} \end{algorithm} +\begin{algorithm}{Rerooting Template} + \sourcecode{graph/reroot.cpp} +\end{algorithm} + +\begin{algorithm}{Virtual Trees} + \sourcecode{graph/virtualTree.cpp} +\end{algorithm} + +\begin{algorithm}{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})} + \end{methods} + \sourcecode{graph/havelHakimi.cpp} +\end{algorithm} + \subsection{Max-Flow} \optional{ -\subsubsection{Push Relabel} -\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} -\end{methods} -\sourcecode{graph/pushRelabel.cpp} + \subsubsection{Push Relabel} + \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} + \end{methods} + \sourcecode{graph/pushRelabel.cpp} } \begin{algorithm}{Min-Cost-Max-Flow} @@ -223,37 +247,27 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/dinicScaling.cpp} \optional{ -\subsubsection{Anwendungen} -\begin{itemize} - \item \textbf{Maximum Edge Disjoint Paths}\newline - Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. - \begin{enumerate} - \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1. - \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Kanten. - \end{enumerate} - \item \textbf{Maximum Independent Paths}\newline - Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen. - \begin{enumerate} - \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1. - \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Knoten. - \end{enumerate} - \item \textbf{Min-Cut}\newline - Der maximale Fluss ist gleich dem minimalen Schnitt. - Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$. - Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten). -\end{itemize} + \subsubsection{Anwendungen} + \begin{itemize} + \item \textbf{Maximum Edge Disjoint Paths}\newline + Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. + \begin{enumerate} + \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1. + \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Kanten. + \end{enumerate} + \item \textbf{Maximum Independent Paths}\newline + Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen. + \begin{enumerate} + \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1. + \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Knoten. + \end{enumerate} + \item \textbf{Min-Cut}\newline + Der maximale Fluss ist gleich dem minimalen Schnitt. + Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$. + Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten). + \end{itemize} } -\begin{algorithm}{Maximum Weight Bipartite Matching} - \begin{methods} - \method{match}{berechnet Matching}{\abs{V}^3} - \end{methods} - \sourcecode{graph/maxWeightBipartiteMatching.cpp} -\end{algorithm} -\vfill\null -\columnbreak - - \begin{algorithm}[optional]{TSP} \begin{methods} \method{TSP}{berechnet eine Tour}{n^2\*2^n} diff --git a/tcr.pdf b/tcr.pdf index 6b38da9..eb0110f 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 3903044dd68da8ac6d589cfc873260dccbf4cd8f Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 21 Apr 2025 14:31:26 +0200 Subject: use awk instead of macro hack --- test/graph/2sat.cpp | 3 --- test/graph/2sat.cpp.awk | 6 ++++++ 2 files changed, 6 insertions(+), 3 deletions(-) create mode 100644 test/graph/2sat.cpp.awk diff --git a/test/graph/2sat.cpp b/test/graph/2sat.cpp index fc3186e..cf37131 100644 --- a/test/graph/2sat.cpp +++ b/test/graph/2sat.cpp @@ -1,9 +1,6 @@ #include "../util.h" #include -#define static vector> adj; static // hacky... #include -#undef static -#undef adj struct RandomClause { int a, b; diff --git a/test/graph/2sat.cpp.awk b/test/graph/2sat.cpp.awk new file mode 100644 index 0000000..d0215d8 --- /dev/null +++ b/test/graph/2sat.cpp.awk @@ -0,0 +1,6 @@ +/scc variablen/ { + print; + print "\tvector> adj;"; + next +} +{ print } -- cgit v1.2.3