diff options
Diffstat (limited to 'content/graph')
| -rw-r--r-- | content/graph/2sat.cpp | 16 | ||||
| -rw-r--r-- | content/graph/LCA_sparse.cpp | 2 | ||||
| -rw-r--r-- | content/graph/bitonicTSP.cpp | 2 | ||||
| -rw-r--r-- | content/graph/cycleCounting.cpp | 2 | ||||
| -rw-r--r-- | content/graph/hopcroftKarp.cpp | 4 | ||||
| -rw-r--r-- | content/graph/stoerWagner.cpp | 8 | ||||
| -rw-r--r-- | content/graph/virtualTree.cpp | 4 |
7 files changed, 19 insertions, 19 deletions
diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp index 75e54e6..2b49fc6 100644 --- a/content/graph/2sat.cpp +++ b/content/graph/2sat.cpp @@ -4,19 +4,19 @@ struct sat2 { sat2(int vars) : n(vars*2), adj(n) {} - static int var(int i) {return i << 1;} // use this! + 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);} + 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 diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index 3e87cde..e391948 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -28,5 +28,5 @@ struct LCA { return visited[st.queryIdempotent(first[u], first[v] + 1)]; } - ll getDepth(int v) {return depth[first[v]];} + ll getDepth(int v) { return depth[first[v]]; } }; diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index eee5082..a6f4c6e 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -13,7 +13,7 @@ auto bitonicTSP() { dp[i] = opt; pre[i] = j; }}} - // return dp.back(); // Länger der Tour + // return dp.back(); // Länge der Tour int j, n = sz(dist) - 1; vector<int> ut, lt = {n, n - 1}; diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp index 6a299ee..471d399 100644 --- a/content/graph/cycleCounting.cpp +++ b/content/graph/cycleCounting.cpp @@ -36,7 +36,7 @@ struct cycles { cur[id].flip(); }}} - bool isCycle(cycle cur) {//cycle must be constrcuted from base + bool isCycle(cycle cur) { // cycle must be constrcuted from base if (cur.none()) return false; init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ for (int i = 0; i < sz(edges); i++) { diff --git a/content/graph/hopcroftKarp.cpp b/content/graph/hopcroftKarp.cpp index c1f5d1c..7c0fec5 100644 --- a/content/graph/hopcroftKarp.cpp +++ b/content/graph/hopcroftKarp.cpp @@ -5,14 +5,14 @@ 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);} + 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 (pairs[u] < 0) { exist = true; continue; } if (dist[pairs[u]] < 0) { dist[pairs[u]] = dist[v] + 1; q.push(pairs[u]); diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 97e667a..0a6f653 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -31,21 +31,21 @@ ll stoer_wagner() { while (!pq.empty()) { int c = pq.top().second; pq.pop(); - if (con[c] < 0) continue; //already seen + if (con[c] < 0) continue; // already seen con[c] = -1; for (auto e : tmp[c]) { - if (con[e.to] >= 0) {//add edge to cut + 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 + } 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?! + if (state.empty()) return 0; // graph is not connected?! merge(state.back().second, t); res = min(res, state.back().first); } diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 6233b27..153ed0b 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -2,11 +2,11 @@ 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];}); + sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); for (int i = 1, n = sz(ind); i < n; i++) { ind.push_back(lca(ind[i - 1], ind[i])); } - sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); + sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); ind.erase(unique(all(ind)), ind.end()); int n = sz(ind); |