diff options
Diffstat (limited to 'graph')
34 files changed, 0 insertions, 1445 deletions
diff --git a/graph/2sat.cpp b/graph/2sat.cpp deleted file mode 100644 index 75e54e6..0000000 --- a/graph/2sat.cpp +++ /dev/null @@ -1,31 +0,0 @@ -struct sat2 { - int n; // + scc variablen - vector<int> 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); - } - 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 solve() { - scc(); //scc code von oben - sol.assign(n, -1); - for (int i = 0; i < n; i += 2) { - if (idx[i] == idx[i + 1]) return false; - sol[i] = idx[i] < idx[i + 1]; - sol[i + 1] = !sol[i]; - } - return true; - } -}; diff --git a/graph/LCA.cpp b/graph/LCA.cpp deleted file mode 100644 index 7debf8f..0000000 --- a/graph/LCA.cpp +++ /dev/null @@ -1,24 +0,0 @@ -vector<vector<int>> adj(); -vector<int> visited(); -vector<int> first(); -vector<int> depth(); - -void initLCA(int gi, int d, int& c) { - visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; - for(int gn : adj[gi]) { - initLCA(gn, d+1, c); - visited[c] = gi, depth[c] = d, c++; -}} - -int getLCA(int a, int b) { - return visited[query(min(first[a], first[b]), max(first[a], first[b]))]; -} - -void exampleUse() { - int c = 0; - visited = vector<int>(2*sz(adj)); - first = vector<int>(sz(adj), 2*sz(adj)); - depth = vector<int>(2*sz(adj)); - initLCA(0, 0, c); - init(depth); -} diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp deleted file mode 100644 index 649e697..0000000 --- a/graph/LCA_sparse.cpp +++ /dev/null @@ -1,32 +0,0 @@ -struct LCA { - vector<ll> depth; - vector<int> visited, first; - int idx; - SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ - - void init(vector<vector<int>>& adj, int root) { - depth.assign(2 * sz(adj), 0); - visited.assign(2 * sz(adj), -1); - first.assign(sz(adj), 2 * sz(adj)); - idx = 0; - dfs(adj, root); - st.init(&depth); - } - - void dfs(vector<vector<int>>& adj, int v, ll d=0, int p=-1) { - visited[idx] = v, depth[idx] = d; - first[v] = min(idx, first[v]), idx++; - - for (int u : adj[v]) { - if (first[u] == 2 * sz(adj)) { - dfs(adj, u, d + 1, v); - visited[idx] = v, depth[idx] = d, idx++; - }}} - - int getLCA(int u, int v) { - if (first[u] > first[v]) swap(u, v); - return visited[st.queryIdempotent(first[u], first[v] + 1)]; - } - - ll getDepth(int v) {return depth[first[v]];} -}; diff --git a/graph/TSP.cpp b/graph/TSP.cpp deleted file mode 100644 index cfb1b4d..0000000 --- a/graph/TSP.cpp +++ /dev/null @@ -1,28 +0,0 @@ -vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten. - -void TSP() { - int n = sz(dist), m = 1 << n; - vector<vector<edge>> dp(n, vector<edge>(m, edge{INF, -1})); - - for (int c = 0; c < n; c++) - dp[c][m-1].dist = dist[c][0], dp[c][m-1].to = 0; - - for (int v = m - 2; v >= 0; v--) { - for (int c = n - 1; c >= 0; c--) { - for (int g = 0; g < n; g++) { - if (g != c && !((1 << g) & v)) { - if ((dp[g][(v | (1 << g))].dist + dist[c][g]) < - dp[c][v].dist) { - dp[c][v].dist = - dp[g][(v | (1 << g))].dist + dist[c][g]; - dp[c][v].to = g; - }}}}} - // return dp[0][1]; // Länge der Tour - - vector<int> tour; tour.push_back(0); int v = 0; - while (tour.back() != 0 || sz(tour) == 1) - tour.push_back(dp[tour.back()] - [(v |= (1 << tour.back()))].to); - // Enthält Knoten 0 zweimal. An erster und letzter Position. - // return tour; -} diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp deleted file mode 100644 index 6819bf3..0000000 --- a/graph/articulationPoints.cpp +++ /dev/null @@ -1,45 +0,0 @@ -vector<vector<Edge>> adj; -vector<int> num; -int counter, rootCount, root; -vector<bool> isArt; -vector<Edge> bridges, st; -vector<vector<Edge>> bcc; - -int dfs(int v, int from = -1) { - int me = num[v] = ++counter, top = me; - for (Edge& e : adj[v]) { - if (e.id == from){} - else if (num[e.to]) { - top = min(top, num[e.to]); - if (num[e.to] < me) st.push_back(e); - } else { - if (v == root) rootCount++; - int si = sz(st); - int up = dfs(e.to, e.id); - top = min(top, up); - if (up >= me) isArt[v] = true; - if (up > me) bridges.push_back(e); - if (up <= me) st.push_back(e); - if (up == me) { - bcc.emplace_back(); - while (sz(st) > si) { - bcc.back().push_back(st.back()); - st.pop_back(); - }}}} - return top; -} - -void find() { - counter = 0; - num.assign(sz(adj), 0); - isArt.assign(sz(adj), false); - bridges.clear(); - st.clear(); - bcc.clear(); - for (int v = 0; v < sz(adj); v++) { - if (!num[v]) { - root = v; - rootCount = 0; - dfs(v); - isArt[v] = rootCount > 1; -}}} diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp deleted file mode 100644 index 4324886..0000000 --- a/graph/bellmannFord.cpp +++ /dev/null @@ -1,17 +0,0 @@ -void bellmannFord(int n, vector<edge> edges, int start) { - vector<ll> dist(n, INF), parent(n, -1); - dist[start] = 0; - - for (int i = 1; i < n; i++) { - for (edge& e : edges) { - if (dist[e.from] != INF && - dist[e.from] + e.cost < dist[e.to]) { - dist[e.to] = dist[e.from] + e.cost; - parent[e.to] = e.from; - }}} - - for (edge& e : edges) { - if (dist[e.from] != INF && - dist[e.from] + e.cost < dist[e.to]) { - // Negativer Kreis gefunden. -}}} //return dist, parent?; diff --git a/graph/bitonicTSP.cpp b/graph/bitonicTSP.cpp deleted file mode 100644 index e8fc2cb..0000000 --- a/graph/bitonicTSP.cpp +++ /dev/null @@ -1,31 +0,0 @@ -vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten. - -void bitonicTSP() { - vector<double> dp(sz(dist), HUGE_VAL); - vector<int> pre(sz(dist)); // nur für Tour - dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0; - for (unsigned int i = 2; i < sz(dist); i++) { - double link = 0; - for (int j = i - 2; j >= 0; j--) { - link += dist[j + 1][j + 2]; - double opt = link + dist[j][i] + dp[j + 1] - dist[j][j + 1]; - if (opt < dp[i]) { - dp[i] = opt; - pre[i] = j; - }}} - // return dp.back(); // Länger der Tour - - int j, n = sz(dist) - 1; - vector<int> ut, lt = {n, n - 1}; - do { - j = pre[n]; - (lt.back() == n ? lt : ut).push_back(j); - for (int i = n - 1; i > j + 1; i--) { - (lt.back() == i ? lt : ut).push_back(i - 1); - } - } while(n = j + 1, j > 0); - (lt.back() == 1 ? lt : ut).push_back(0); - reverse(all(lt)); - lt.insert(lt.end(), all(ut)); - //return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. -} diff --git a/graph/bitonicTSPsimple.cpp b/graph/bitonicTSPsimple.cpp deleted file mode 100644 index 96ae5bd..0000000 --- a/graph/bitonicTSPsimple.cpp +++ /dev/null @@ -1,28 +0,0 @@ -vector<vector<double>> dist; // Entfernungen zwischen Punkten. -vector<vector<double>> dp; - -double get(int p1, int p2) { - int v = max(p1, p2) + 1; - if (v == sz(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; - if (dp[p1][p2] >= 0.0) return dp[p1][p2]; - double tryLR = dist[p1][v] + get(v, p2); - double tryRL = dist[p2][v] + get(p1, v); - return dp[p1][p2] = min(tryLR, tryRL); -} - -void bitonicTour() { - dp = vector<vector<double>>(sz(dist), - vector<double>(sz(dist), -1)); - get(0, 0); - // return dp[0][0]; // Länger der Tour - vector<int> lr = {0}, rl = {0}; - for (int p1 = 0, p2 = 0, v; (v = max(p1, p2)+1) < sz(dist);) { - if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { - lr.push_back(v); p1 = v; - } else { - rl.push_back(v); p2 = v; - }} - lr.insert(lr.end(), rl.rbegin(), rl.rend()); - // Enthält Knoten 0 zweimal. An erster und letzter Position. - // return lr; -} diff --git a/graph/blossom.cpp b/graph/blossom.cpp deleted file mode 100644 index 7bd494a..0000000 --- a/graph/blossom.cpp +++ /dev/null @@ -1,82 +0,0 @@ -struct GM { - vector<vector<int>> adj; - // pairs ist der gematchte knoten oder n - vector<int> pairs, first, que; - vector<pair<int, int>> label; - int head, tail; - - GM(int n) : adj(n), pairs(n + 1, n), first(n + 1, n), - que(n), label(n + 1, {-1, -1}) {} - - void rematch(int u, int v) { - int t = pairs[u]; pairs[u] = v; - if (pairs[t] != u) return; - if (label[u].second == -1) { - pairs[t] = label[u].first; - rematch(pairs[t], t); - } else { - auto [x, y] = label[u]; - rematch(x, y); - rematch(y, x); - }} - - int findFirst(int v) { - return label[first[v]].first < 0 ? first[v] - : first[v] = findFirst(first[v]); - } - - void relabel(int x, int y) { - int r = findFirst(x); - int s = findFirst(y); - if (r == s) return; - auto h = label[r] = label[s] = {~x, y}; - int join; - while (true) { - if (s != sz(adj)) swap(r, s); - r = findFirst(label[pairs[r]].first); - if (label[r] == h) { - join = r; - break; - } else { - label[r] = h; - }} - for (int v : {first[x], first[y]}) { - for (; v != join; v = first[label[pairs[v]].first]) { - label[v] = {x, y}; - first[v] = join; - que[tail++] = v; - }}} - - bool augment(int v) { - label[v] = {sz(adj), -1}; - first[v] = sz(adj); - head = tail = 0; - for (que[tail++] = v; head < tail;) { - int x = que[head++]; - for (int y : adj[x]) { - if (pairs[y] == sz(adj) && y != v) { - pairs[y] = x; - rematch(x, y); - return true; - } else if (label[y].first >= 0) { - relabel(x, y); - } else if (label[pairs[y]].first == -1) { - label[pairs[y]].first = x; - first[pairs[y]] = y; - que[tail++] = pairs[y]; - }}} - return false; - } - - int match() { - int matching = head = tail = 0; - for (int v = 0; v < sz(adj); v++) { - if (pairs[v] < sz(adj) || !augment(v)) continue; - matching++; - for (int i = 0; i < tail; i++) - label[que[i]] = label[pairs[que[i]]] = {-1, -1}; - label[sz(adj)] = {-1, -1}; - } - return matching; - } -}; diff --git a/graph/bronKerbosch.cpp b/graph/bronKerbosch.cpp deleted file mode 100644 index ceeb668..0000000 --- a/graph/bronKerbosch.cpp +++ /dev/null @@ -1,24 +0,0 @@ -using bits = bitset<64>; -vector<bits> adj, cliques; - -void addEdge(int a, int b) { - if (a != b) adj[a][b] = adj[b][a] = 1; -} - -void bronKerboschRec(bits R, bits P, bits X) { - if (!P.any() && !X.any()) { - cliques.push_back(R); - } else { - int q = min(P._Find_first(), X._Find_first()); - bits cands = P & ~adj[q]; - for (int i = 0; i < sz(adj); i++) if (cands[i]){ - R[i] = 1; - bronKerboschRec(P & adj[i], X & adj[i], R); - R[i] = P[i] = 0; - X[i] = 1; -}}} - -void bronKerbosch() { - cliques.clear(); - bronKerboschRec({}, {(1ull << sz(adj)) - 1}, {}); -} diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp deleted file mode 100644 index 90ae654..0000000 --- a/graph/capacityScaling.cpp +++ /dev/null @@ -1,44 +0,0 @@ -struct edge { - int from, to; - ll f, c; -}; - -vector<edge> edges; -vector<vector<int>> adj; -int s, t, dfsCounter; -vector<int> visited; -ll capacity; - -void addEdge(int from, int to, ll c) { - adj[from].push_back(sz(edges)); - edges.push_back({from, to, 0, c}); - adj[to].push_back(sz(edges)); - edges.push_back({to, from, 0, 0}); -} - -bool dfs(int v) { - if (v == t) return true; - if (visited[v] == dfsCounter) return false; - visited[v] = dfsCounter; - for (int id : adj[v]) { - if (edges[id].c >= capacity && dfs(edges[id].to)) { - edges[id].c -= capacity; edges[id ^ 1].c += capacity; - edges[id].f += capacity; edges[id ^ 1].f -= capacity; - return true; - }} - return false; -} - -ll maxFlow(int source, int target) { - capacity = 1ll << 62; - s = source; - t = target; - ll flow = 0; - visited.assign(sz(adj), 0); - dfsCounter = 0; - while (capacity) { - while (dfsCounter++, dfs(s)) flow += capacity; - capacity /= 2; - } - return flow; -} diff --git a/graph/centroid.cpp b/graph/centroid.cpp deleted file mode 100644 index 2494464..0000000 --- a/graph/centroid.cpp +++ /dev/null @@ -1,21 +0,0 @@ -vector<int> s; -void dfs_sz(int v, int from = -1) { - s[v] = 1; - for (int u : adj[v]) if (u != from) { - dfs_sz(u, v); - s[v] += s[u]; -}} - -pair<int, int> dfs_cent(int v, int from, int n) { - for (int u : adj[v]) if (u != from) { - if (2 * s[u] == n) return {v, u}; - if (2 * s[u] > n) return dfs_cent(u, v, n); - } - return {v, -1}; -} - -pair<int, int> find_centroid(int root) { - s.resize(sz(adj)); - dfs_sz(root); - return dfs_cent(root, -1, s[root]); -} diff --git a/graph/connect.cpp b/graph/connect.cpp deleted file mode 100644 index 98b5b25..0000000 --- a/graph/connect.cpp +++ /dev/null @@ -1,31 +0,0 @@ -struct connect { - int n; - vector<pair<int, int>> edges; - LCT lct; // min LCT no updates required - - connect(int n, int m) : n(n), edges(m), lct(n+m) {} - - bool connected(int u, int v) { - return lct.connected(&lct.nodes[u], &lct.nodes[v]); - } - - void addEdge(int u, int v, int id) { - lct.nodes[id + n] = LCT::Node(id + n, id + n); - edges[id] = {u, v}; - if (connected(u, v)) { - int old = lct.query(&lct.nodes[u], &lct.nodes[v]); - if (old < id) eraseEdge(old); - } - if (!connected(u, v)) { - lct.link(&lct.nodes[u], &lct.nodes[id + n]); - lct.link(&lct.nodes[v], &lct.nodes[id + n]); - }} - - void eraseEdge(ll id) { - if (connected(edges[id].first, edges[id].second) && - lct.query(&lct.nodes[edges[id].first], - &lct.nodes[edges[id].second]) == id) { - lct.cut(&lct.nodes[edges[id].first], &lct.nodes[id + n]); - lct.cut(&lct.nodes[edges[id].second], &lct.nodes[id + n]); - }} -}; diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp deleted file mode 100644 index bd7a219..0000000 --- a/graph/cycleCounting.cpp +++ /dev/null @@ -1,64 +0,0 @@ -constexpr int maxEdges = 128; -using cycle = bitset<maxEdges>; -struct cylces { - vector<vector<pair<int, int>>> adj; - vector<bool> seen; - vector<cycle> paths, base; - vector<pair<int, int>> edges; - - cylces(int n) : adj(n), seen(n), paths(n) {} - - void addEdge(int u, int v) { - adj[u].push_back({v, sz(edges)}); - adj[v].push_back({u, sz(edges)}); - edges.push_back({u, v}); - } - - void addBase(cycle cur) { - for (cycle o : base) { - o ^= cur; - if (o._Find_first() > cur._Find_first()) cur = o; - } - if (cur.any()) base.push_back(cur); - } - - void findBase(int v = 0, int from = -1, cycle cur = {}) { - if (adj.empty()) return; - if (seen[v]) { - addBase(cur ^ paths[v]); - } else { - seen[v] = true; - paths[v] = cur; - for (auto [u, id] : adj[v]) { - if (u == from) continue; - cur[id].flip(); - findBase(u, v, cur); - cur[id].flip(); - }}} - - //cycle must be constrcuted from base - bool isCycle(cycle cur) { - if (cur.none()) return false; - init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ - for (int i = 0; i < sz(edges); i++) { - if (cur[i]) { - cur[i] = false; - if (findSet(edges[i].first) == - findSet(edges[i].second)) break; - unionSets(edges[i].first, edges[i].second); - }} - return cur.none(); - }; - - int count() { - findBase(); - int res = 0; - for (int i = 1; i < (1 << sz(base)); i++) { - cycle cur; - for (int j = 0; j < sz(base); j++) { - if (((i >> j) & 1) != 0) cur ^= base[j]; - if (isCycle(cur)) res++; - } - return res; - } -}; diff --git a/graph/dfs.tex b/graph/dfs.tex deleted file mode 100644 index 1e6705f..0000000 --- a/graph/dfs.tex +++ /dev/null @@ -1,16 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|X|XIXIX|} - \hline - Kantentyp $(v, w)$ & \code{dfs[v] < dfs[w]} & \code{fin[v] > fin[w]} & \code{seen[w]} \\ - %$(v, w)$ & \code{dfs[w]} & \code{fin[w]} & \\ - \hline - in-tree & \code{true} & \code{true} & \code{false} \\ - \grayhline - forward & \code{true} & \code{true} & \code{true} \\ - \grayhline - backward & \code{false} & \code{false} & \code{true} \\ - \grayhline - cross & \code{false} & \code{true} & \code{true} \\ - \hline -\end{tabularx} -\end{expandtable} diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp deleted file mode 100644 index 57071b0..0000000 --- a/graph/dijkstra.cpp +++ /dev/null @@ -1,21 +0,0 @@ -using path = pair<ll, int>; //dist, destination - -void dijkstra(const vector<vector<path>>& adj, int start) { - priority_queue<path, vector<path>, greater<path>> pq; - vector<ll> dist(sz(adj), INF); - vector<int> prev(sz(adj), -1); - dist[start] = 0; pq.emplace(0, start); - - while (!pq.empty()) { - auto [dv, v] = pq.top(); pq.pop(); - if (dv > dist[v]) continue; // WICHTIG! - - for (auto [du, u] : adj[v]) { - ll newDist = dv + du; - if (newDist < dist[u]) { - dist[u] = newDist; - prev[u] = v; - pq.emplace(dist[u], u); - }}} - //return dist, prev; -} diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp deleted file mode 100644 index f4e833a..0000000 --- a/graph/dinicScaling.cpp +++ /dev/null @@ -1,51 +0,0 @@ -struct Edge { - int to, rev; - ll f, c; -}; - -vector<vector<Edge>> adj; -int s, t; -vector<int> pt, dist; - -void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); -} - -bool bfs(ll lim) { - dist.assign(sz(adj), -1); - dist[s] = 0; - queue<int> q({s}); - while (!q.empty() && dist[t] < 0) { - int v = q.front(); q.pop(); - for (Edge& e : adj[v]) { - if (dist[e.to] < 0 && e.c - e.f >= lim) { - dist[e.to] = dist[v] + 1; - q.push(e.to); - }}} - return dist[t] >= 0; -} - -bool dfs(int v, ll flow) { - if (v == t) return true; - for (; pt[v] < sz(adj[v]); pt[v]++) { - Edge& e = adj[v][pt[v]]; - if (dist[e.to] != dist[v] + 1) continue; - if (e.c - e.f >= flow && dfs(e.to, flow)) { - e.f += flow; - adj[e.to][e.rev].f -= flow; - return true; - }} - return false; -} - -ll maxFlow(int source, int target) { - s = source, t = target; - ll flow = 0; - for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { - while (bfs(lim)) { - pt.assign(sz(adj), 0); - while (dfs(s, lim)) flow += lim; - }} - return flow; -} diff --git a/graph/euler.cpp b/graph/euler.cpp deleted file mode 100644 index a5ea192..0000000 --- a/graph/euler.cpp +++ /dev/null @@ -1,23 +0,0 @@ -vector<vector<int>> idx; -vector<int> to, validIdx, cycle; -vector<bool> used; - -void addEdge(int u, int v) { - idx[u].push_back(sz(to)); - to.push_back(v); - used.push_back(false); - idx[v].push_back(sz(to)); // für ungerichtet - to.push_back(u); - used.push_back(false); -} - -void euler(int v) { // init idx und validIdx - for (;validIdx[v] < sz(idx[v]); validIdx[v]++) { - if (!used[idx[v][validIdx[v]]]) { - int u = to[idx[v][validIdx[v]]]; - used[idx[v][validIdx[v]]] = true; - used[idx[v][validIdx[v]] ^ 1] = true; // für ungerichtet - euler(u); - }} - cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge. -} diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp deleted file mode 100644 index fb6263e..0000000 --- a/graph/floydWarshall.cpp +++ /dev/null @@ -1,26 +0,0 @@ -vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten. -vector<vector<int>> pre; - -void floydWarshall() { - pre.assign(sz(dist), vector<int>(sz(dist), -1)); - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { - if (dist[i][j] < INF) { - pre[i][j] = j; - }}} - - for (int k = 0; k < sz(dist); k++) { - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { - if (dist[i][j] > dist[i][k] + dist[k][j]) { - dist[i][j] = dist[i][k] + dist[k][j]; - pre[i][j] = pre[i][k]; -}}}}} - -vector<int> getPath(int u, int v) { - //return dist[u][v]; // Pfadlänge u -> v - if (pre[u][v] < 0) return {}; - vector<int> path = {v}; - while (u != v) path.push_back(u = pre[u][v]); - return path; //Pfad u -> v -} diff --git a/graph/graph.tex b/graph/graph.tex deleted file mode 100644 index 9232090..0000000 --- a/graph/graph.tex +++ /dev/null @@ -1,276 +0,0 @@ -\section{Graphen} - -\begin{algorithm}{Kruskal} - \begin{methods}[ll] - berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ - \end{methods} - \sourcecode{graph/kruskal.cpp} -\end{algorithm} - -\begin{algorithm}{Minimale Spannbäume} - \paragraph{Schnitteigenschaft} - Für jeden Schnitt $C$ im Graphen gilt: - Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. - ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) - - \paragraph{Kreiseigenschaft} - Für jeden Kreis $K$ im Graphen gilt: - Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. -\end{algorithm} - -\begin{algorithm}{Heavy-Light Decomposition} - \begin{methods} - \method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})} - \end{methods} - \textbf{Wichtig:} Intervalle sind halboffen - - Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. - \sourcecode{graph/hld.cpp} -\end{algorithm} - -\begin{algorithm}{Lowest Common Ancestor} - \begin{methods} - \method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})} - \method{getLCA}{findet LCA}{1} - \method{getDepth}{berechnet Distanz zur Wurzel im DFS-Baum}{1} - \end{methods} - \sourcecode{graph/LCA_sparse.cpp} -\end{algorithm} - -\begin{algorithm}{Centroids} - \begin{methods} - \method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}} - \end{methods} - \sourcecode{graph/centroid.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>> adj} 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}{Baum-Isomorphie} - \begin{methods} - \method{treeLabel}{berechnet kanonischen Namen für einen Baum}{\abs{V}\*\log(\abs{V})} - \end{methods} - \sourcecode{graph/treeIsomorphism.cpp} -\end{algorithm} - -\subsection{Kürzeste Wege} - -\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} - -\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{i} liegt auf einem negativen Kreis $\Leftrightarrow$ \code{dist[i][i] < 0}. -\end{itemize} -\sourcecode{graph/floydWarshall.cpp} - -\subsubsection{Matrix-Algorithmus} -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} \cdot b_{k\smash{j}}$ - -\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{eraseEdge}{entfernt Kante \code{id}}{\log(n)} - \end{methods} - \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} - \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} - -\begin{algorithm}{2-SAT} - \sourcecode{graph/2sat.cpp} -\end{algorithm} - -\begin{algorithm}{Maximal Cliques} - \begin{methods} - \method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}} - \method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1} - \end{methods} - \sourcecode{graph/bronKerbosch.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} - -\begin{algorithm}{Wert des maximalen Matchings} - Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$ - \sourcecode{graph/matching.cpp} -\end{algorithm} - -\begin{algorithm}{Allgemeines maximales Matching} - \begin{methods} - \method{match}{berechnet algemeines Matching}{\abs{E}\*\abs{V}\*\log(\abs{V})} - \end{methods} - \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}{Maximal 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} - -\begin{algorithm}{Global Mincut} - \begin{methods} - \method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}\abs{E}+\abs{V}^2\*\log(\abs{E})} - \method{merge(a,b)}{merged Knoten $b$ in Knoten $a$}{\abs{E}} - \end{methods} - \textbf{Tipp:} Cut Rekonstruktion mit \code{unionFind} für Partitionierung oder \code{vector<bool>} für edge id's im cut. - \sourcecode{graph/stoerWagner.cpp} -\end{algorithm} - -\subsection{Max-Flow} -\optional{ -\subsubsection{Capacity Scaling} -\begin{methods} - \method{maxFlow}{gut bei dünn besetzten Graphen.}{\abs{E}^2\*\log(C)} - \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} -\end{methods} -\sourcecode{graph/capacityScaling.cpp} -} - -\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} -} - -\begin{algorithm}{Min-Cost-Max-Flow} - \begin{methods} - \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} - \end{methods} - \sourcecode{graph/minCostMaxFlow.cpp} -\end{algorithm} - -\subsubsection{Dinic's Algorithm mit Capacity Scaling} -\begin{methods} - \method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}} - \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} -\end{methods} -\sourcecode{graph/dinicScaling.cpp} -\vfill\null -\columnbreak - -\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} -} - -\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} - \end{methods} - \sourcecode{graph/TSP.cpp} -\end{algorithm} - -\begin{algorithm}[optional]{Bitonic TSP} - \begin{methods} - \method{bitonicTSP}{berechnet eine Bitonische Tour}{n^2} - \end{methods} - \sourcecode{graph/bitonicTSPsimple.cpp} -\end{algorithm} - diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp deleted file mode 100644 index cbd6991..0000000 --- a/graph/havelHakimi.cpp +++ /dev/null @@ -1,18 +0,0 @@ -vector<vector<int>> havelHakimi(const vector<int>& deg) { - priority_queue<pair<int, int>> pq; - for (int i = 0; i < sz(deg); i++) { - if (deg[i] > 0) pq.push({deg[i], i}); - } - vector<vector<int>> adj; - while (!pq.empty()) { - auto [degV, v] = pq.top(); pq.pop(); - if (sz(pq) < degV) return {}; //impossible - vector<pair<int, int>> todo(degV); - for (auto& e : todo) e = pq.top(), pq.pop(); - for (auto [degU, u] : todo) { - adj[v].push_back(u); - adj[u].push_back(v); - if (degU > 1) pq.push({degU - 1, u}); - }} - return adj; -} diff --git a/graph/hld.cpp b/graph/hld.cpp deleted file mode 100644 index 65d3f5c..0000000 --- a/graph/hld.cpp +++ /dev/null @@ -1,44 +0,0 @@ -vector<vector<int>> adj; -vector<int> sz, in, out, nxt, par; -int counter; - -void dfs_sz(int v = 0, int from = -1) { - for (auto& u : adj[v]) if (u != from) { - dfs_sz(u, v); - sz[v] += sz[u]; - if (adj[v][0] == from || sz[u] > sz[adj[v][0]]) { - swap(u, adj[v][0]); //changes adj! -}}} - -void dfs_hld(int v = 0, int from = -1) { - par[v] = from; - in[v] = counter++; - for (int u : adj[v]) if (u != from) { - nxt[u] = (u == adj[v][0]) ? nxt[v] : u; - dfs_hld(u, v); - } - out[v] = counter; -} - -void init(int root = 0) { - int n = sz(adj); - sz.assign(n, 1), nxt.assign(n, root), par.assign(n, -1); - in.resize(n), out.resize(n); - counter = 0; - dfs_sz(root); - dfs_hld(root); -} - -template<typename F> -void for_intervals(int u, int v, F&& f) { - for (;; v = par[nxt[v]]) { - if (in[v] < in[u]) swap(u, v); - f(max(in[u], in[nxt[v]]), in[v] + 1); - if (in[nxt[v]] <= in[u]) return; -}} - -int get_lca(int u, int v) { - for (;; v = par[nxt[v]]) { - if (in[v] < in[u]) swap(u, v); - if (in[nxt[v]] <= in[u]) return u; -}} diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp deleted file mode 100644 index c1f5d1c..0000000 --- a/graph/hopcroftKarp.cpp +++ /dev/null @@ -1,47 +0,0 @@ -vector<vector<int>> adj; -// pairs ist der gematchte Knoten oder -1 -vector<int> pairs, dist, ptr; - -bool bfs(int l) { - queue<int> q; - for(int v = 0; v < l; v++) { - if (pairs[v] < 0) {dist[v] = 0; q.push(v);} - else dist[v] = -1; - } - bool exist = false; - while(!q.empty()) { - int v = q.front(); q.pop(); - for (int u : adj[v]) { - if (pairs[u] < 0) {exist = true; continue;} - if (dist[pairs[u]] < 0) { - dist[pairs[u]] = dist[v] + 1; - q.push(pairs[u]); - }}} - return exist; -} - -bool dfs(int v) { - for (; ptr[v] < sz(adj[v]); ptr[v]++) { - int u = adj[v][ptr[v]]; - if (pairs[u] < 0 || - (dist[pairs[u]] > dist[v] && dfs(pairs[u]))) { - pairs[u] = v; pairs[v] = u; - return true; - }} - return false; -} - -int hopcroft_karp(int l) { // l = #Knoten links - int ans = 0; - pairs.assign(sz(adj), -1); - dist.resize(l); - // Greedy Matching, optionale Beschleunigung. - for (int v = 0; v < l; v++) for (int u : adj[v]) - if (pairs[u] < 0) {pairs[u] = v; pairs[v] = u; ans++; break;} - while(bfs(l)) { - ptr.assign(l, 0); - for(int v = 0; v < l; v++) { - if (pairs[v] < 0) ans += dfs(v); - }} - return ans; -} diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp deleted file mode 100644 index 987d30b..0000000 --- a/graph/kruskal.cpp +++ /dev/null @@ -1,9 +0,0 @@ -sort(all(edges)); -vector<Edge> mst; -ll cost = 0; -for (Edge& e : edges) { - if (findSet(e.from) != findSet(e.to)) { - unionSets(e.from, e.to); - mst.push_back(e); - cost += e.cost; -}} diff --git a/graph/matching.cpp b/graph/matching.cpp deleted file mode 100644 index 2513604..0000000 --- a/graph/matching.cpp +++ /dev/null @@ -1,23 +0,0 @@ -constexpr int MOD=1'000'000'007, I=10; -vector<vector<ll>> adj, mat; - -int max_matching() { - int ans = 0; - mat.assign(sz(adj), {}); - for (int _ = 0; _ < I; _++) { - for (int v = 0; v < sz(adj); v++) { - 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]; - }}} - gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ - int rank = 0; - for (auto& row : mat) { - if (*min_element(all(row)) != 0) rank++; - } - ans = max(ans, rank / 2); - } - return ans; -} diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp deleted file mode 100644 index e928387..0000000 --- a/graph/maxCarBiMatch.cpp +++ /dev/null @@ -1,25 +0,0 @@ -vector<vector<int>> adj; -vector<int> pairs; // Der gematchte Knoten oder -1. -vector<bool> visited; - -bool dfs(int v) { - if (visited[v]) return false; - visited[v] = true; - for (int u : adj[v]) if (pairs[u] < 0 || dfs(pairs[u])) { - pairs[u] = v; pairs[v] = u; return true; - } - return false; -} - -int kuhn(int l) { // l = #Knoten links. - pairs.assign(sz(adj), -1); - int ans = 0; - // Greedy Matching. Optionale Beschleunigung. - for (int v = 0; v < l; v++) for (int u : adj[v]) - if (pairs[u] < 0) {pairs[u] = v; pairs[v] = u; ans++; break;} - for (int v = 0; v < l; v++) if (pairs[v] < 0) { - visited.assign(l, false); - ans += dfs(v); - } - return ans; // Größe des Matchings. -} diff --git a/graph/maxWeightBipartiteMatching.cpp b/graph/maxWeightBipartiteMatching.cpp deleted file mode 100644 index a2b0a80..0000000 --- a/graph/maxWeightBipartiteMatching.cpp +++ /dev/null @@ -1,50 +0,0 @@ -double costs[N_LEFT][N_RIGHT]; - -// Es muss l<=r sein! (sonst Endlosschleife) -double match(int l, int r) { - vector<double> lx(l), ly(r); - //xy is matching from l->r, yx from r->l, or -1 - vector<int> xy(l, -1), yx(r, -1); - vector<pair<double, int>> slack(r); - - for (int x = 0; x < l; x++) - lx[x] = *max_element(costs[x], costs[x] + r); - for (int root = 0; root < l; root++) { - vector<int> aug(r, -1); - vector<bool> s(l); - s[root] = true; - for (int y = 0; y < r; y++) { - slack[y] = {lx[root] + ly[y] - costs[root][y], root}; - } - int y = -1; - while (true) { - double delta = INF; - int x = -1; - for (int yy = 0; yy < r; yy++) { - if (aug[yy] < 0 && slack[yy].first < delta) { - tie(delta, x) = slack[yy]; - y = yy; - }} - if (delta > 0) { - for (int x = 0; x < l; x++) if (s[x]) lx[x] -= delta; - for (int y = 0; y < r; y++) { - if (aug[y] >= 0) ly[y] += delta; - else slack[y].first -= delta; - }} - aug[y] = x; - x = yx[y]; - if (x < 0) break; - s[x] = true; - for (int y = 0; y < r; y++) { - if (aug[y] < 0) { - double alt = lx[x] + ly[y] - costs[x][y]; - if (slack[y].first > alt) { - slack[y] = {alt, x}; - }}}} - while (y >= 0) { - yx[y] = aug[y]; - swap(y, xy[aug[y]]); - }} - return accumulate(all(lx), 0.0) + - accumulate(all(ly), 0.0); // Wert des Matchings -} diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp deleted file mode 100644 index 14a222c..0000000 --- a/graph/minCostMaxFlow.cpp +++ /dev/null @@ -1,66 +0,0 @@ -constexpr ll INF = 1LL << 60; // Größer als der maximale Fluss. -struct MinCostFlow { - struct edge { - int to; - ll f, cost; - }; - vector<edge> edges; - vector<vector<int>> adj; - vector<int> pref, con; - vector<ll> dist; - const int s, t; - ll maxflow, mincost; - - MinCostFlow(int n, int source, int target) : - adj(n), s(source), t(target) {}; - - void addEdge(int u, int v, ll c, ll cost) { - adj[u].push_back(sz(edges)); - edges.push_back({v, c, cost}); - adj[v].push_back(sz(edges)); - edges.push_back({u, 0, -cost}); - } - - bool SPFA() { - pref.assign(sz(adj), -1); - dist.assign(sz(adj), INF); - vector<bool> inqueue(sz(adj)); - queue<int> queue; - dist[s] = 0; - queue.push(s); - pref[s] = s; - inqueue[s] = true; - while (!queue.empty()) { - int cur = queue.front(); queue.pop(); - inqueue[cur] = false; - for (int id : adj[cur]) { - int to = edges[id].to; - if (edges[id].f > 0 && - dist[to] > dist[cur] + edges[id].cost) { - dist[to] = dist[cur] + edges[id].cost; - pref[to] = cur; - con[to] = id; - if (!inqueue[to]) { - inqueue[to] = true; - queue.push(to); - }}}} - return pref[t] != -1; - } - - void extend() { - ll w = INF; - for (int u = t; pref[u] != u; u = pref[u]) - w = min(w, edges[con[u]].f); - maxflow += w; - mincost += dist[t] * w; - for (int u = t; pref[u] != u; u = pref[u]) { - edges[con[u]].f -= w; - edges[con[u] ^ 1].f += w; - }} - - void mincostflow() { - con.assign(sz(adj), 0); - maxflow = mincost = 0; - while (SPFA()) extend(); - } -}; diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp deleted file mode 100644 index 904aec6..0000000 --- a/graph/pushRelabel.cpp +++ /dev/null @@ -1,64 +0,0 @@ -struct Edge { - int to, rev; - ll f, c; -}; - -vector<vector<Edge>> adj; -vector<vector<int>> hs; -vector<ll> ec; -vector<int> cur, H; - -void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0}); -} - -void addFlow(Edge& e, ll f) { - if (ec[e.to] == 0 && f > 0) - hs[H[e.to]].push_back(e.to); - e.f += f; - adj[e.to][e.rev].f -= f; - ec[e.to] += f; - ec[adj[e.to][e.rev].to] -= f; -} - -ll maxFlow(int s, int t) { - int n = sz(adj); - hs.assign(2*n, {}); - ec.assign(n, 0); - cur.assign(n, 0); - H.assign(n, 0); - H[s] = n; - ec[t] = 1;//never set t to active... - vector<int> co(2*n); - co[0] = n - 1; - for (Edge& e : adj[s]) addFlow(e, e.c); - for (int hi = 0;;) { - while (hs[hi].empty()) if (!hi--) return -ec[s]; - int v = hs[hi].back(); - hs[hi].pop_back(); - while (ec[v] > 0) { - if (cur[v] == sz(adj[v])) { - H[v] = 2*n; - for (int i = 0; i < sz(adj[v]); i++) { - Edge& e = adj[v][i]; - if (e.c - e.f > 0 && - H[v] > H[e.to] + 1) { - H[v] = H[e.to] + 1; - cur[v] = i; - }} - co[H[v]]++; - if (!--co[hi] && hi < n) { - for (int i = 0; i < n; i++) { - if (hi < H[i] && H[i] < n) { - co[H[i]]--; - H[i] = n + 1; - }}} - hi = H[v]; - } else { - Edge& e = adj[v][cur[v]]; - if (e.c - e.f > 0 && H[v] == H[e.to] + 1) { - addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f)); - } else { - cur[v]++; -}}}}} diff --git a/graph/reroot.cpp b/graph/reroot.cpp deleted file mode 100644 index 4c6a748..0000000 --- a/graph/reroot.cpp +++ /dev/null @@ -1,62 +0,0 @@ -// Usual Tree DP can be broken down in 4 steps: -// - Initialize dp[v] = identity -// - Iterate over all children w and take a value for w -// by looking at dp[w] and possibly the edge label of v -> w -// - combine the values of those children -// usually this operation should be commutative and associative -// - finalize the dp[v] after iterating over all children -struct Reroot { - using T = ll; - - // identity element - T E() {} - // x: dp value of child - // e: index of edge going to child - T takeChild(T x, int e) {} - T comb(T x, T y) {} - // called after combining all dp values of children - T fin(T x, int v) {} - - vector<vector<pair<int, int>>> g; - vector<int> ord, pae; - vector<T> dp; - - T dfs(int v) { - ord.push_back(v); - for (auto [w, e] : g[v]) { - g[w].erase(find(all(g[w]), pair(v, e^1))); - pae[w] = e^1; - dp[v] = comb(dp[v], takeChild(dfs(w), e)); - } - return dp[v] = fin(dp[v], v); - } - - vector<T> solve(int n, vector<pair<int, int>> edges) { - g.resize(n); - for (int i = 0; i < n-1; i++) { - g[edges[i].first].emplace_back(edges[i].second, 2*i); - g[edges[i].second].emplace_back(edges[i].first, 2*i+1); - } - pae.assign(n, -1); - dp.assign(n, E()); - dfs(0); - vector<T> updp(n, E()), res(n, E()); - for (int v : ord) { - vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1); - if (v != 0) pref[0] = takeChild(updp[v], pae[v]); - for (int i = 0; i < sz(g[v]); i++){ - auto [u, w] = g[v][i]; - pref[i+1] = suff[i] = takeChild(dp[u], w); - pref[i+1] = comb(pref[i], pref[i+1]); - } - for (int i = sz(g[v])-1; i >= 0; i--) { - suff[i] = comb(suff[i], suff[i+1]); - } - for (int i = 0; i < sz(g[v]); i++) { - updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); - } - res[v] = fin(pref.back(), v); - } - return res; - } -}; diff --git a/graph/scc.cpp b/graph/scc.cpp deleted file mode 100644 index ac9a40b..0000000 --- a/graph/scc.cpp +++ /dev/null @@ -1,32 +0,0 @@ -vector<vector<int>> adj, sccs; -int counter; -vector<bool> inStack; -vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten. - -void visit(int v) { - int old = low[v] = counter++; - 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 (old == low[v]) { - sccs.push_back({}); - for (int u = -1; u != v;) { - u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sz(sccs) - 1; - sccs.back().push_back(u); -}}} - -void scc() { - inStack.assign(sz(adj), false); - low.assign(sz(adj), -1); - idx.assign(sz(adj), -1); - sccs.clear(); - - counter = 0; - for (int i = 0; i < sz(adj); i++) { - if (low[i] < 0) visit(i); -}} diff --git a/graph/stoerWagner.cpp b/graph/stoerWagner.cpp deleted file mode 100644 index 97e667a..0000000 --- a/graph/stoerWagner.cpp +++ /dev/null @@ -1,53 +0,0 @@ -struct Edge { - int from, to; - ll cap; -}; - -vector<vector<Edge>> adj, tmp; -vector<bool> erased; - -void merge(int u, int v) { - tmp[u].insert(tmp[u].end(), all(tmp[v])); - tmp[v].clear(); - erased[v] = true; - for (auto& vec : tmp) { - for (Edge& e : vec) { - if (e.from == v) e.from = u; - if (e.to == v) e.to = u; -}}} - -ll stoer_wagner() { - ll res = INF; - tmp = adj; - erased.assign(sz(tmp), false); - for (int i = 1; i < sz(tmp); i++) { - int s = 0; - while (erased[s]) s++; - priority_queue<pair<ll, int>> pq; - pq.push({0, s}); - vector<ll> con(sz(tmp)); - ll cur = 0; - vector<pair<ll, int>> state; - while (!pq.empty()) { - int c = pq.top().second; - pq.pop(); - if (con[c] < 0) continue; //already seen - con[c] = -1; - for (auto e : tmp[c]) { - if (con[e.to] >= 0) {//add edge to cut - con[e.to] += e.cap; - pq.push({con[e.to], e.to}); - cur += e.cap; - } else if (e.to != c) {//remove edge from cut - cur -= e.cap; - }} - state.push_back({cur, c}); - } - int t = state.back().second; - state.pop_back(); - if (state.empty()) return 0; //graph is not connected?! - merge(state.back().second, t); - res = min(res, state.back().first); - } - return res; -} diff --git a/graph/treeIsomorphism.cpp b/graph/treeIsomorphism.cpp deleted file mode 100644 index 4e9ddce..0000000 --- a/graph/treeIsomorphism.cpp +++ /dev/null @@ -1,15 +0,0 @@ -vector<vector<int>> adj; -map<vector<int>, int> known; - -int treeLabel(int v, int from = -1) { - vector<int> children; - for (int u : adj[v]) { - if (u == from) continue; - children.push_back(treeLabel(u, v)); - } - sort(all(children)); - if (known.find(children) == known.end()) { - known[children] = sz(known); - } - return known[children]; -} diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp deleted file mode 100644 index 2fcea80..0000000 --- a/graph/virtualTree.cpp +++ /dev/null @@ -1,22 +0,0 @@ -// needs dfs in- and out- time and lca function -vector<int> in, out; - -void virtualTree(vector<int> ind) { // indices of used nodes - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - for (int i=0; i<sz(a)-1; i++) { - ind.push_back(lca(ind[i], ind[i+1])); - } - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - ind.erase(unique(all(ind)), ind.end()); - - int n = ind.size(); - vector<vector<int>> tree(n); - vector<int> st = {0}; - for (int i=1; i<n; i++) { - while (in[ind[i]] >= out[ind[st.back()]]) st.pop_back(); - tree[st.back()].push_back(i); - st.push(i); - } - // virtual directed tree with n nodes, original indices in ind - // weights can be calculated, e.g. with binary lifting -} |