summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--graph/LCA_sparse.cpp26
-rw-r--r--graph/articulationPoints.cpp12
-rw-r--r--graph/blossom.cpp32
-rw-r--r--graph/capacityScaling.cpp10
-rw-r--r--graph/centroid.cpp8
-rw-r--r--graph/connect.cpp18
-rw-r--r--graph/cycleCounting.cpp24
-rw-r--r--graph/dijkstra.cpp16
-rw-r--r--graph/dinicScaling.cpp6
-rw-r--r--graph/euler.cpp26
-rw-r--r--graph/hopcroftKarp.cpp38
-rw-r--r--graph/kruskal.cpp4
-rw-r--r--graph/matching.cpp12
-rw-r--r--graph/maxCarBiMatch.cpp12
-rw-r--r--graph/pushRelabel.cpp64
-rw-r--r--graph/pushRelabel2.cpp48
-rw-r--r--graph/pushRelabel3.cpp30
-rw-r--r--graph/stoerWagner.cpp20
-rw-r--r--graph/treeIsomorphism.cpp8
19 files changed, 207 insertions, 207 deletions
diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp
index a56dafa..2a864c0 100644
--- a/graph/LCA_sparse.cpp
+++ b/graph/LCA_sparse.cpp
@@ -4,29 +4,29 @@ struct LCA {
int idx;
SparseTable st; //sparse table von oben
- void init(vector<vector<int>>& g, int root) {
- depth.assign(2 * sz(g), 0);
- visited.assign(2 * sz(g), -1);
- first.assign(sz(g), 2 * sz(g));
+ 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;
- visit(g, root);
+ dfs(adj, root);
st.init(&depth);
}
- void visit(vector<vector<int>>& g, int v, ll d=0, int p=-1) {
+ 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 w : g[v]) {
- if (first[w] == 2 * sz(g)) {
- visit(g, w, d + 1, v);
+ 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 a, int b) {
- if (first[a] > first[b]) swap(a, b);
- return visited[st.queryIdempotent(first[a], first[b] + 1)];
+ 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 a) {return depth[first[a]];}
+ ll getDepth(int v) {return depth[first[v]];}
};
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
index 4e3dff7..6819bf3 100644
--- a/graph/articulationPoints.cpp
+++ b/graph/articulationPoints.cpp
@@ -1,14 +1,14 @@
-vector<vector<edge>> adj;
+vector<vector<Edge>> adj;
vector<int> num;
int counter, rootCount, root;
vector<bool> isArt;
-vector<edge> bridges, st;
-vector<vector<edge>> bcc;
+vector<Edge> bridges, st;
+vector<vector<Edge>> bcc;
-int dfs(int v, int parent = -1) {
+int dfs(int v, int from = -1) {
int me = num[v] = ++counter, top = me;
- for (edge& e : adj[v]) {
- if (e.id == parent){}
+ 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);
diff --git a/graph/blossom.cpp b/graph/blossom.cpp
index dd9d000..7bd494a 100644
--- a/graph/blossom.cpp
+++ b/graph/blossom.cpp
@@ -8,21 +8,21 @@ struct GM {
GM(int n) : adj(n), pairs(n + 1, n), first(n + 1, n),
que(n), label(n + 1, {-1, -1}) {}
- void rematch(int v, int w) {
- int t = pairs[v]; pairs[v] = w;
- if (pairs[t] != v) return;
- if (label[v].second == -1) {
- pairs[t] = label[v].first;
+ 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[v];
+ auto [x, y] = label[u];
rematch(x, y);
rematch(y, x);
}}
- int findFirst(int u) {
- return label[first[u]].first < 0 ? first[u]
- : first[u] = findFirst(first[u]);
+ int findFirst(int v) {
+ return label[first[v]].first < 0 ? first[v]
+ : first[v] = findFirst(first[v]);
}
void relabel(int x, int y) {
@@ -47,14 +47,14 @@ struct GM {
que[tail++] = v;
}}}
- bool augment(int u) {
- label[u] = {sz(adj), -1};
- first[u] = sz(adj);
+ bool augment(int v) {
+ label[v] = {sz(adj), -1};
+ first[v] = sz(adj);
head = tail = 0;
- for (que[tail++] = u; head < tail;) {
+ for (que[tail++] = v; head < tail;) {
int x = que[head++];
for (int y : adj[x]) {
- if (pairs[y] == sz(adj) && y != u) {
+ if (pairs[y] == sz(adj) && y != v) {
pairs[y] = x;
rematch(x, y);
return true;
@@ -70,8 +70,8 @@ struct GM {
int match() {
int matching = head = tail = 0;
- for (int u = 0; u < sz(adj); u++) {
- if (pairs[u] < sz(adj) || !augment(u)) continue;
+ 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};
diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp
index 84af162..90ae654 100644
--- a/graph/capacityScaling.cpp
+++ b/graph/capacityScaling.cpp
@@ -16,11 +16,11 @@ void addEdge(int from, int to, ll c) {
edges.push_back({to, from, 0, 0});
}
-bool dfs(int x) {
- if (x == t) return true;
- if (visited[x] == dfsCounter) return false;
- visited[x] = dfsCounter;
- for (int id : adj[x]) {
+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;
diff --git a/graph/centroid.cpp b/graph/centroid.cpp
index c5187a5..2494464 100644
--- a/graph/centroid.cpp
+++ b/graph/centroid.cpp
@@ -1,13 +1,13 @@
vector<int> s;
-void dfs_sz(int v, int parent = -1) {
+void dfs_sz(int v, int from = -1) {
s[v] = 1;
- for (int u : adj[v]) if (u != parent) {
+ for (int u : adj[v]) if (u != from) {
dfs_sz(u, v);
s[v] += s[u];
}}
-pair<int, int> dfs_cent(int v, int parent, int n) {
- for (int u : adj[v]) if (u != parent) {
+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);
}
diff --git a/graph/connect.cpp b/graph/connect.cpp
index a7b2811..98b5b25 100644
--- a/graph/connect.cpp
+++ b/graph/connect.cpp
@@ -5,20 +5,20 @@ struct connect {
connect(int n, int m) : n(n), edges(m), lct(n+m) {}
- bool connected(int a, int b) {
- return lct.connected(&lct.nodes[a], &lct.nodes[b]);
+ bool connected(int u, int v) {
+ return lct.connected(&lct.nodes[u], &lct.nodes[v]);
}
- void addEdge(int a, int b, int id) {
+ void addEdge(int u, int v, int id) {
lct.nodes[id + n] = LCT::Node(id + n, id + n);
- edges[id] = {a, b};
- if (connected(a, b)) {
- int old = lct.query(&lct.nodes[a], &lct.nodes[b]);
+ 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(a, b)) {
- lct.link(&lct.nodes[a], &lct.nodes[id + n]);
- lct.link(&lct.nodes[b], &lct.nodes[id + n]);
+ 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) {
diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp
index bf32874..9772706 100644
--- a/graph/cycleCounting.cpp
+++ b/graph/cycleCounting.cpp
@@ -8,10 +8,10 @@ struct cylces {
cylces(int n) : adj(n), seen(n), paths(n) {}
- 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});
+ 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) {
@@ -22,17 +22,17 @@ struct cylces {
if (cur.any()) base.push_back(cur);
}
- void findBase(int c = 0, int p = -1, cycle cur = {}) {
+ void findBase(int v = 0, int from = -1, cycle cur = {}) {
if (adj.empty()) return;
- if (seen[c]) {
- addBase(cur ^ paths[c]);
+ if (seen[v]) {
+ addBase(cur ^ paths[v]);
} else {
- seen[c] = true;
- paths[c] = cur;
- for (auto [to, id] : adj[c]) {
- if (to == p) continue;
+ seen[v] = true;
+ paths[v] = cur;
+ for (auto [u, id] : adj[v]) {
+ if (u == from) continue;
cur[id].flip();
- findBase(to, c, cur);
+ findBase(u, v, cur);
cur[id].flip();
}}}
diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
index aa938ec..57071b0 100644
--- a/graph/dijkstra.cpp
+++ b/graph/dijkstra.cpp
@@ -7,15 +7,15 @@ void dijkstra(const vector<vector<path>>& adj, int start) {
dist[start] = 0; pq.emplace(0, start);
while (!pq.empty()) {
- auto [dc, c] = pq.top(); pq.pop();
- if (dc > dist[c]) continue; // WICHTIG!
+ auto [dv, v] = pq.top(); pq.pop();
+ if (dv > dist[v]) continue; // WICHTIG!
- for (auto [dx, x] : adj[c]) {
- ll newDist = dc + dx;
- if (newDist < dist[x]) {
- dist[x] = newDist;
- prev[x] = c;
- pq.emplace(newDist, x);
+ 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
index a795be1..f4e833a 100644
--- a/graph/dinicScaling.cpp
+++ b/graph/dinicScaling.cpp
@@ -17,10 +17,10 @@ bool bfs(ll lim) {
dist[s] = 0;
queue<int> q({s});
while (!q.empty() && dist[t] < 0) {
- int cur = q.front(); q.pop();
- for (Edge& e : adj[cur]) {
+ 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[cur] + 1;
+ dist[e.to] = dist[v] + 1;
q.push(e.to);
}}}
return dist[t] >= 0;
diff --git a/graph/euler.cpp b/graph/euler.cpp
index 6ef3c13..a5ea192 100644
--- a/graph/euler.cpp
+++ b/graph/euler.cpp
@@ -2,22 +2,22 @@ vector<vector<int>> idx;
vector<int> to, validIdx, cycle;
vector<bool> used;
-void addEdge(int a, int b) {
- idx[a].push_back(sz(to));
- to.push_back(b);
+void addEdge(int u, int v) {
+ idx[u].push_back(sz(to));
+ to.push_back(v);
used.push_back(false);
- idx[b].push_back(sz(to)); // für ungerichtet
- to.push_back(a);
+ idx[v].push_back(sz(to)); // für ungerichtet
+ to.push_back(u);
used.push_back(false);
}
-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
- euler(nn);
+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(n); // Zyklus in umgekehrter Reihenfolge.
+ cycle.push_back(v); // Zyklus in umgekehrter Reihenfolge.
}
diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp
index 61ec469..c1f5d1c 100644
--- a/graph/hopcroftKarp.cpp
+++ b/graph/hopcroftKarp.cpp
@@ -4,28 +4,28 @@ vector<int> pairs, dist, ptr;
bool bfs(int l) {
queue<int> q;
- for(int i = 0; i < l; i++) {
- if (pairs[i] < 0) {dist[i] = 0; q.push(i);}
- else dist[i] = -1;
+ 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 u = q.front(); q.pop();
- for (int v : adj[u]) {
- if (pairs[v] < 0) {exist = true; continue;}
- if (dist[pairs[v]] < 0) {
- dist[pairs[v]] = dist[u] + 1;
- q.push(pairs[v]);
+ 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 u) {
- for (; ptr[u] < sz(adj[u]); ptr[u]++) {
- int v = adj[u][ptr[u]];
- if (pairs[v] < 0 ||
- (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) {
- pairs[v] = u; pairs[u] = v;
+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;
@@ -36,12 +36,12 @@ int hopcroft_karp(int l) { // l = #Knoten links
pairs.assign(sz(adj), -1);
dist.resize(l);
// Greedy Matching, optionale Beschleunigung.
- for (int i = 0; i < l; i++) for (int w : adj[i])
- if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;}
+ 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 i = 0; i < l; i++) {
- if (pairs[i] < 0) ans += dfs(i);
+ 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
index d21da01..987d30b 100644
--- a/graph/kruskal.cpp
+++ b/graph/kruskal.cpp
@@ -1,7 +1,7 @@
sort(all(edges));
-vector<edge> mst;
+vector<Edge> mst;
ll cost = 0;
-for (edge& e : edges) {
+for (Edge& e : edges) {
if (findSet(e.from) != findSet(e.to)) {
unionSets(e.from, e.to);
mst.push_back(e);
diff --git a/graph/matching.cpp b/graph/matching.cpp
index 613cabb..f059351 100644
--- a/graph/matching.cpp
+++ b/graph/matching.cpp
@@ -5,12 +5,12 @@ int max_matching() {
int ans = 0;
mat.assign(sz(adj), {});
for (int _ = 0; _ < I; _++) {
- for (int i = 0; i < sz(adj); i++) {
- mat[i].assign(sz(adj), 0);
- for (int j : adj[i]) {
- if (j < i) {
- mat[i][j] = rand() % (MOD - 1) + 1;
- mat[j][i] = MOD - mat[i][j];
+ 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 unten
int rank = 0;
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
index 588568b..0c5ac43 100644
--- a/graph/maxCarBiMatch.cpp
+++ b/graph/maxCarBiMatch.cpp
@@ -5,8 +5,8 @@ vector<bool> visited;
bool dfs(int v) {
if (visited[v]) return false;
visited[v] = true;
- for (auto w : adj[v]) if (pairs[w] < 0 || dfs(pairs[w])) {
- pairs[w] = v; pairs[v] = w; return true;
+ for (int u : adj[v]) if (pairs[u] < 0 || dfs(pairs[u])) {
+ pairs[u] = v; pairs[v] = u; return true;
}
return false;
}
@@ -15,11 +15,11 @@ int kuhn(int n) { // n = #Knoten links.
pairs.assign(sz(adj), -1);
int ans = 0;
// Greedy Matching. Optionale Beschleunigung.
- for (int i = 0; i < n; i++) for (auto w : adj[i])
- if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;}
- for (int i = 0; i < n; i++) if (pairs[i] < 0) {
+ 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 < n; v++) if (pairs[v] < 0) {
visited.assign(n, false);
- ans += dfs(i);
+ ans += dfs(v);
}
return ans; // Größe des Matchings.
}
diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp
index 182fa12..da3ada7 100644
--- a/graph/pushRelabel.cpp
+++ b/graph/pushRelabel.cpp
@@ -1,73 +1,73 @@
struct PushRelabel {
- vector<vector<long long>> capacitie, flow;
- vector<long long> excess;
+ vector<vector<ll>> capacitie, flow;
+ vector<ll> excess;
vector<int> height, seen, list;
int n;
PushRelabel(int n) {
this->n = n;
- capacities.assign(n, vector<long long>(n));
- flow.assign(n, vector<long long>(n));
+ capacities.assign(n, vector<ll>(n));
+ flow.assign(n, vector<ll>(n));
excess.assign(n, 0);
height.assign(n, 0);
seen.assign(n, 0);
list.assign(n - 2, 0);
}
- inline void addEdge(int u, int v, long long c) {capacities[u][v] += c;}
+ inline void addEdge(int u, int v, ll c) {capacities[u][v] += c;}
void push(int u, int v) {
- long long send = min(excess[u], capacities[u][v] - flow[u][v]);
+ ll send = min(excess[u], capacities[u][v] - flow[u][v]);
flow[u][v] += send; flow[v][u] -= send;
excess[u] -= send; excess[v] += send;
}
- void relabel(int u) {
+ void relabel(int v) {
int minHeight = INT_INF;
- for (int v = 0; v < n; v++) {
- if (capacities[u][v] - flow[u][v] > 0) {
- minHeight = min(minHeight, height[v]);
- height[u] = minHeight + 1;
+ for (int u = 0; u < n; u++) {
+ if (capacities[v][u] - flow[v][u] > 0) {
+ minHeight = min(minHeight, height[u]);
+ height[v] = minHeight + 1;
}}}
- void discharge(int u) {
- while (excess[u] > 0) {
- if (seen[u] < n) {
- int v = seen[u];
- if (capacities[u][v] - flow[u][v] > 0 && height[u] > height[v]) {
- push(u, v);
- } else seen[u]++;
+ void discharge(int v) {
+ while (excess[v] > 0) {
+ if (seen[v] < n) {
+ int u = seen[v];
+ if (capacities[v][u] - flow[v][u] > 0 && height[v] > height[u]) {
+ push(v, u);
+ } else seen[v]++;
} else {
- relabel(u);
- seen[u] = 0;
+ relabel(v);
+ seen[v] = 0;
}}}
- void moveToFront(int u) {
- int temp = list[u];
- for (int i = u; i > 0; i--) list[i] = list[i - 1];
+ void moveToFront(int v) {
+ int temp = list[v];
+ for (int u = v; u > 0; u--) list[u] = list[u - 1];
list[0] = temp;
}
- long long maxFlow(int source, int target) {
- for (int i = 0, p = 0; i < n; i++)
- if (i != source && i != target) list[p++] = i;
+ ll maxFlow(int source, int target) {
+ for (int v = 0, p = 0; v < n; v++)
+ if (v != source && v != target) list[p++] = v;
height[source] = n;
excess[source] = INF;
- for (int i = 0; i < n; i++) push(source, i);
+ for (int v = 0; v < n; v++) push(source, v);
int p = 0;
while (p < n - 2) {
- int u = list[p], oldHeight = height[u];
- discharge(u);
- if (height[u] > oldHeight) {
+ int v = list[p], oldHeight = height[v];
+ discharge(v);
+ if (height[v] > oldHeight) {
moveToFront(p);
p = 0;
} else p++;
}
- long long maxflow = 0;
- for (int i = 0; i < n; i++) maxflow += flow[source][i];
+ ll maxflow = 0;
+ for (int v = 0; v < n; v++) maxflow += flow[source][v];
return maxflow;
}
};
diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp
index 270cd35..5619d88 100644
--- a/graph/pushRelabel2.cpp
+++ b/graph/pushRelabel2.cpp
@@ -27,39 +27,39 @@ void globalRelabel(int n, int t) {
que.assign(n+1, 0);
int qh = 0, qt = 0;
for (que[qt++] = t; qh < qt;) {
- int u = que[qh++], h = height[u] + 1;
- for (int id : adj[u]) {
+ int v = que[qh++], h = height[v] + 1;
+ for (int id : adj[v]) {
if (height[edges[id].to] == n && edges[id ^ 1].c - edges[id ^ 1].f > 0) {
ccount[height[edges[id].to] = h]++;
que[qt++] = edges[id].to;
}}}
llist.assign(n+1, {});
dlist.assign(n+1, {});
- for (int u = 0; u < n; u++) {
- if (height[u] < n) {
- iter[u] = dlist[height[u]].insert(dlist[height[u]].begin(), u);
- if (excess[u] > 0) llist[height[u]].push_back(u);
+ for (int v = 0; v < n; v++) {
+ if (height[v] < n) {
+ iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v);
+ if (excess[v] > 0) llist[height[v]].push_back(v);
}}
highest = highestActive = height[que[qt - 1]];
}
-void push(int u, int id) {
- int v = edges[id].to;
- ll df = min(excess[u], edges[id].c - edges[id].f);
+void push(int v, int id) {
+ int u = edges[id].to;
+ ll df = min(excess[v], edges[id].c - edges[id].f);
edges[id].f += df;
edges[id^1].f -= df;
- excess[u] -= df;
- excess[v] += df;
- if (0 < excess[v] && excess[v] <= df) llist[height[v]].push_back(v);
+ excess[v] -= df;
+ excess[u] += df;
+ if (0 < excess[u] && excess[u] <= df) llist[height[u]].push_back(u);
}
-void discharge(int n, int u) {
+void discharge(int n, int v) {
int nh = n;
- for (int id : adj[u]) {
+ for (int id : adj[v]) {
if (edges[id].c - edges[id].f > 0) {
- if (height[u] == height[edges[id].to] + 1) {
- push(u, id);
- if (!excess[u]) return;
+ if (height[v] == height[edges[id].to] + 1) {
+ push(v, id);
+ if (!excess[v]) return;
} else {
nh = min(nh, height[edges[id].to] + 1);
}}}
@@ -71,11 +71,11 @@ void discharge(int n, int u) {
}
highest = h - 1;
} else {
- --ccount[h], iter[u] = dlist[h].erase(iter[u]), height[u] = nh;
+ --ccount[h], iter[v] = dlist[h].erase(iter[v]), height[v] = nh;
if (nh == n) return;
- ++ccount[nh], iter[u] = dlist[nh].insert(dlist[nh].begin(), u);
+ ++ccount[nh], iter[v] = dlist[nh].insert(dlist[nh].begin(), v);
highest = max(highest, highestActive = nh);
- llist[nh].push_back(u);
+ llist[nh].push_back(v);
}}
ll maxFlow(int s, int t) {
@@ -86,8 +86,8 @@ ll maxFlow(int s, int t) {
height.assign(n, 0);
height[s] = n;
iter.resize(n);
- for (int i = 0; i < n; i++) {
- if (i != s) iter[i] = dlist[height[i]].insert(dlist[height[i]].begin(), i);
+ for (int v = 0; v < n; v++) {
+ if (v != s) iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v);
}
ccount.assign(n, 0);
ccount[0] = n-1;
@@ -101,9 +101,9 @@ ll maxFlow(int s, int t) {
highestActive--;
continue;
}
- int u = llist[highestActive].back();
+ int v = llist[highestActive].back();
llist[highestActive].pop_back();
- discharge(n, u);
+ discharge(n, v);
}
return excess[t] + inf;
}
diff --git a/graph/pushRelabel3.cpp b/graph/pushRelabel3.cpp
index 3c17fcb..4f383f6 100644
--- a/graph/pushRelabel3.cpp
+++ b/graph/pushRelabel3.cpp
@@ -37,30 +37,30 @@ ll maxFlow(int s, int t) {
for (int id : adj[s]) addFlow(id, edges[id].c);
for (int hi = 0;;) {
while (hs[hi].empty()) if (!hi--) return -ec[s];
- int u = hs[hi].back();
+ int v = hs[hi].back();
hs[hi].pop_back();
- while (ec[u] > 0) {
- if (cur[u] == sz(adj[u])) {
- H[u] = 2*n;
- for (int i = 0; i < sz(adj[u]); i++) {
- int id = adj[u][i];
+ while (ec[v] > 0) {
+ if (cur[v] == sz(adj[v])) {
+ H[v] = 2*n;
+ for (int i = 0; i < sz(adj[v]); i++) {
+ int id = adj[v][i];
if (edges[id].c - edges[id].f > 0 &&
- H[u] > H[edges[id].to] + 1) {
- H[u] = H[edges[id].to] + 1;
- cur[u] = i;
+ H[v] > H[edges[id].to] + 1) {
+ H[v] = H[edges[id].to] + 1;
+ cur[v] = i;
}}
- co[H[u]]++;
+ 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[u];
+ hi = H[v];
} else {
- auto e = edges[adj[u][cur[u]]];
- if (e.c - e.f > 0 && H[u] == H[e.to] + 1) {
- addFlow(adj[u][cur[u]], min(ec[u], e.c - e.f));
+ auto e = edges[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[u]++;
+ cur[v]++;
}}}}}
diff --git a/graph/stoerWagner.cpp b/graph/stoerWagner.cpp
index 655f5aa..97e667a 100644
--- a/graph/stoerWagner.cpp
+++ b/graph/stoerWagner.cpp
@@ -1,19 +1,19 @@
-struct edge {
+struct Edge {
int from, to;
ll cap;
};
-vector<vector<edge>> adj, tmp;
+vector<vector<Edge>> adj, tmp;
vector<bool> erased;
-void merge(int a, int b) {
- tmp[a].insert(tmp[a].end(), all(tmp[b]));
- tmp[b].clear();
- erased[b] = true;
- for (auto& v : tmp) {
- for (auto&e : v) {
- if (e.from == b) e.from = a;
- if (e.to == b) e.to = a;
+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() {
diff --git a/graph/treeIsomorphism.cpp b/graph/treeIsomorphism.cpp
index 7a1be5b..4e9ddce 100644
--- a/graph/treeIsomorphism.cpp
+++ b/graph/treeIsomorphism.cpp
@@ -1,11 +1,11 @@
vector<vector<int>> adj;
map<vector<int>, int> known;
-int treeLabel(int root, int p = -1) {
+int treeLabel(int v, int from = -1) {
vector<int> children;
- for (int x : adj[root]) {
- if (x == p) continue;
- children.push_back(treeLabel(x, root));
+ for (int u : adj[v]) {
+ if (u == from) continue;
+ children.push_back(treeLabel(u, v));
}
sort(all(children));
if (known.find(children) == known.end()) {
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 22:39:28 +0000