squezed in new code :D

5 files changed, 84 insertions, 88 deletions

diff --git a/graph/2sat.cpp b/graph/2sat.cpp
index 2ebb11a..4e47ba0 100644
--- a/graph/2sat.cpp
+++ b/graph/2sat.cpp
@@ -4,19 +4,19 @@ struct sat2 {
 
 	sat2(int vars) : n(vars*2), adjlist(vars*2) {};
 
-	static int var(int i) {return i << 1;}
+	static int var(int i) {return i << 1;} // use this!
 
-	void addImpl(int v1, int v2) {
-		adjlist[v1].push_back(v2);
-		adjlist[1^v2].push_back(1^v1);
+	void addImpl(int a, int b) {
+		adjlist[a].push_back(b);
+		adjlist[1^b].push_back(1^a);
 	}
-	void addEquiv(int v1, int v2) {addImpl(v1, v2); addImpl(v2, v1);}
-	void addOr(int v1, int v2) {addImpl(1^v1, v2);}
-	void addXor(int v1, int v2) {addOr(v1, v2); addOr(1^v1, 1^v2);}
-	void addTrue(int v1) {addImpl(1^v1, v1);}
-	void addFalse(int v1) {addTrue(1^v1);}
-	void addAnd(int v1, int v2) {addTrue(v1); addTrue(v2);}
-	void addNand(int v1, int v2) {addOr(1^v1, 1^v2);}
+	void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);}
+	void addOr(int a, int b) {addImpl(1^a, b);}
+	void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);}
+	void addTrue(int a) {addImpl(1^a, a);}
+	void addFalse(int a) {addTrue(1^a);}
+	void addAnd(int a, int b) {addTrue(a); addTrue(b);}
+	void addNand(int a, int b) {addOr(1^a, 1^b);}
 
 	bool solvable() {
 		scc(); //scc code von oben
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
index 0df1eeb..fb18d36 100644
--- a/graph/articulationPoints.cpp
+++ b/graph/articulationPoints.cpp
@@ -29,7 +29,7 @@ int dfs(int v, int parent = -1) {
 	return top;
 }
 
-void findArticulationPoints() {
+void find() {
 	counter = 0;
 	num.assign(sz(adjlist), 0);
 	isArt.assign(sz(adjlist), false);
diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp
index b64b230..c3fe457 100644
--- a/graph/cycleCounting.cpp
+++ b/graph/cycleCounting.cpp
@@ -1,15 +1,14 @@
-constexpr ll maxEdges = 128;
+constexpr int maxEdges = 128;
 using cycle = bitset<maxEdges>;
 struct cylces {
-	ll n;
-	vector<vector<pair<ll, ll>>> adj;
+	vector<vector<pair<int, int>>> adj;
 	vector<bool> seen;
 	vector<cycle> paths, base;
-	vector<pair<ll, ll>> edges;
+	vector<pair<int, int>> edges;
 
-	cylces(ll n) : n(n), adj(n), seen(n), paths(n) {}
+	cylces(int n) : adj(n), seen(n), paths(n) {}
 
-	void addEdge(ll a, ll b) {
+	void addEdge(int a, int b) {
 		adj[a].push_back({b, sz(edges)});
 		adj[b].push_back({a, sz(edges)});
 		edges.push_back({a, b});
@@ -23,8 +22,8 @@ struct cylces {
 		if (cur.any()) base.push_back(cur);
 	}
 
-	void findBase(ll c = 0, ll p = -1, cycle cur = {}) {
-		if (n == 0) return;
+	void findBase(int c = 0, int p = -1, cycle cur = {}) {
+		if (adj.empty()) return;
 		if (seen[c]) {
 			addBase(cur ^ paths[c]);
 		} else {
@@ -40,8 +39,8 @@ struct cylces {
 	//cycle must be constrcuted from base
 	bool isCycle(cycle cur) {
 		if (cur.none()) return false;
-		init(n);
-		for (ll i = 0; i < sz(edges); i++) {
+		init(sz(adj)); // union find
+		for (int i = 0; i < sz(edges); i++) {
 			if (cur[i]) {
 				cur[i] = false;
 				if (findSet(edges[i].first) == 
@@ -51,12 +50,12 @@ struct cylces {
 		return cur.none();
 	};
 
-	ll count() {
+	int count() {
 		findBase();
-		ll res = 0;
-		for (ll i = 1; i < (1ll << sz(base)); i++) {
+		int res = 0;
+		for (int i = 1; i < (1 << sz(base)); i++) {
 			cycle cur;
-			for (ll j = 0; j < sz(base); j++) {
+			for (int j = 0; j < sz(base); j++) {
 				if (((i >> j) & 1) != 0) cur ^= base[j];
 			if (isCycle(cur)) res++;
 		}
diff --git a/graph/euler.cpp b/graph/euler.cpp
index 0907ab2..6ef3c13 100644
--- a/graph/euler.cpp
+++ b/graph/euler.cpp
@@ -6,21 +6,18 @@ void addEdge(int a, int b) {
 	idx[a].push_back(sz(to));
 	to.push_back(b);
 	used.push_back(false);
-	idx[b].push_back(sz(to)); //für ungerichtet
+	idx[b].push_back(sz(to)); // für ungerichtet
 	to.push_back(a);
 	used.push_back(false);
 }
 
-// Findet Eulerzyklus an Knoten n startend.
-// init idx und validIdx
-void euler(int n) {
+void euler(int n) { // init idx und validIdx
 	for (;validIdx[n] < sz(idx[n]); validIdx[n]++) {
 		if (!used[idx[n][validIdx[n]]]) {
 			int nn = to[idx[n][validIdx[n]]];
 			used[idx[n][validIdx[n]]] = true;
-			used[idx[n][validIdx[n]] ^ 1] = true; //für ungerichtet
+			used[idx[n][validIdx[n]] ^ 1] = true; // für ungerichtet
 			euler(nn);
 	}}
-	// Zyklus in cycle in umgekehrter Reihenfolge.
-	cycle.push_back(n);
+	cycle.push_back(n); // Zyklus in umgekehrter Reihenfolge.
 }
diff --git a/graph/graph.tex b/graph/graph.tex
index a26661d..47f1d75 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -68,52 +68,6 @@ Sei $d_{ij}$ die Distanzmatrix von $G$, dann gibt $d_{ij}^k$ die kürzeste Dista
 
 Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{ij}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{ij} = a_{ij} \* b_{ij} = \sum a_{ik} + b_{kj}$
 
-\begin{algorithm}{Artikulationspunkte, Brücken und BCC}
-	\begin{methods}
-		\method{findArticulationPoints}{berechnet Artikulationspunkte,}{\abs{V}+\abs{E}}
-		\method{}{Brücken und BCC}{}
-	\end{methods}
-	\textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC.
-	\sourcecode{graph/articulationPoints.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
-	\begin{methods}
-		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
-	\end{methods}
-	\sourcecode{graph/scc.cpp}
-\end{algorithm}
-
-\begin{algorithm}{2-SAT}
-	\sourcecode{graph/2sat.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Eulertouren}
-	\begin{methods}
-		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
-	\end{methods}
-	\sourcecode{graph/euler.cpp}
-	\begin{itemize}
-		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
-		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
-		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
-		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
-		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-		Die Existenz muss separat geprüft werden.
-	\end{itemize}
-\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}
-
 \begin{algorithm}{Lowest Common Ancestor}
 	\begin{methods}
 		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
@@ -132,14 +86,33 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
 	\sourcecode{graph/hld.cpp}
 \end{algorithm}
+\clearpage
 
-\begin{algorithm}{Dynamic Connectivity}
+\begin{algorithm}{Maximal Cliques}
 	\begin{methods}
-		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
-		\method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)}
-		\method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)}
+		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
+		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
 	\end{methods}
-	\sourcecode{graph/connect.cpp}
+	\sourcecode{graph/bronKerbosch.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}{Strongly Connected Components (\textsc{Tarjan})}
+	\begin{methods}
+		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
+	\end{methods}
+	\sourcecode{graph/scc.cpp}
+\end{algorithm}
+
+\begin{algorithm}{2-SAT}
+	\sourcecode{graph/2sat.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Global Mincut}
@@ -254,10 +227,37 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \end{algorithm}
 }
 
-\begin{algorithm}{Maximal Cliques}
+\begin{algorithm}{Cycle Counting}
 	\begin{methods}
-		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
-		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
+		\method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
+		\method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
 	\end{methods}
-	\sourcecode{graph/bronKerbosch.cpp}
+	\begin{itemize}
+		\item jeder Zyklus ist das xor von einträgen in \code{base}.
+	\end{itemize}
+	\sourcecode{graph/cycleCounting.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Eulertouren}
+	\begin{methods}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
+	\end{methods}
+	\sourcecode{graph/euler.cpp}
+	\begin{itemize}
+		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
+		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
+\end{algorithm}
+
+\begin{algorithm}{Dynamic Connectivity}
+	\begin{methods}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)}
+	\end{methods}
+	\sourcecode{graph/connect.cpp}
 \end{algorithm}