diff options
| -rw-r--r-- | graph/articulationPoints.cpp | 47 | ||||
| -rw-r--r-- | graph/graph.tex | 3 | ||||
| -rw-r--r-- | math/math.tex | 7 | ||||
| -rw-r--r-- | tcr.pdf | bin | 291824 -> 297317 bytes |
4 files changed, 53 insertions, 4 deletions
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp new file mode 100644 index 0000000..b99a286 --- /dev/null +++ b/graph/articulationPoints.cpp @@ -0,0 +1,47 @@ +vector< vector<int> > adjlist; +vector<int> low; +vector<int> d; +vector<bool> isArtPoint; +vector< vector<int> > bridges; //nur fuer Bruecken +int counter = 0; + +void visit(int v, int parent) { + d[v] = low[v] = ++counter; + int numVisits = 0, maxlow = 0; + + for (vector<int>::iterator vit = adjlist[v].begin(); vit != adjlist[v].end(); vit++) { + if (d[*vit] == 0) { + numVisits++; + visit(*vit, v); + if (low[*vit] > maxlow) { + maxlow = low[*vit]; + } + + if (low[*vit] > d[v]) { //nur fuer Bruecken + bridges[v].push_back(*vit); bridges[*vit].push_back(v); + } + + low[v] = min(low[v], low[*vit]); + } else { + if (d[*vit] < low[v]) { + low[v] = d[*vit]; + } + } + } + + if (parent == -1) { + if (numVisits > 1) isArtPoint[v] = true; + } else { + if (maxlow >= d[v]) isArtPoint[v] = true; + } +} + +void findArticulationPoints() { + low.clear(); low.resize(adjlist.size()); + d.clear(); d.assign(adjlist.size(), 0); + isArtPoint.clear(); isArtPoint.assign(adjlist.size(), false); + bridges.clear(); isBridge.resize(adjlist.size()); //nur fuer Bruecken + for (int v = 0; v < (int)adjlist.size(); v++) { + if (d[v] == 0) visit(v, -1); + } +}
\ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 2bf395c..5fc725e 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,5 +13,8 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} +\subsection{Artikulationspunkte und Brücken} +\lstinputlisting{graph/articulationPoints.cpp} + \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.cpp}
\ No newline at end of file diff --git a/math/math.tex b/math/math.tex index 71e5648..973103a 100644 --- a/math/math.tex +++ b/math/math.tex @@ -17,10 +17,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \end{description} \lstinputlisting{math/multInv.cpp} - -\subsubsection{Primzahlsieb von Eratosthenes} -\lstinputlisting{math/primeSieve.cpp} - \subsubsection{Faktorisierung} \lstinputlisting{math/factor.cpp} @@ -32,3 +28,6 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp} + +\subsection{Primzahlsieb von Eratosthenes} +\lstinputlisting{math/primeSieve.cpp} Binary files differ |