summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--datastructures/sparseTable.cpp11
-rw-r--r--datastructures/sparseTableDisjoint.cpp26
-rw-r--r--graph/2sat.cpp6
-rw-r--r--graph/LCA.cpp10
-rw-r--r--graph/articulationPoints.cpp10
-rw-r--r--graph/blossom.cpp20
-rw-r--r--graph/capacityScaling.cpp10
-rw-r--r--graph/dijkstra.cpp8
-rw-r--r--graph/graph.tex4
-rw-r--r--graph/matching.cpp12
-rw-r--r--graph/maxCarBiMatch.cpp8
-rw-r--r--graph/minCostMaxFlow.cpp18
-rw-r--r--graph/pushRelabel2.cpp14
-rw-r--r--graph/pushRelabel3.cpp20
-rw-r--r--graph/scc.cpp14
-rw-r--r--graph/stoerWagner.cpp4
16 files changed, 111 insertions, 84 deletions
diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp
index 61a6802..7578695 100644
--- a/datastructures/sparseTable.cpp
+++ b/datastructures/sparseTable.cpp
@@ -3,15 +3,16 @@ struct SparseTable {
vector<ll> *a;
int better(int lidx, int ridx) {
- return a->at(lidx) <= a->at(ridx) ? lidx : ridx;
+ return a[lidx] <= a[ridx] ? lidx : ridx;
}
void init(vector<ll> *vec) {
- a = vec;
- st.assign(__lg(sz(*a)) + 1, vector<int>(sz(*a)));
+ int n = sz(*vec);
+ a = vec->data();
+ st.assign(__lg(n) + 1, vector<int>(n));
iota(all(st[0]), 0);
- for (int j = 0; (2 << j) <= sz(*a); j++) {
- for (int i = 0; i + (2 << j) <= sz(*a); i++) {
+ for (int j = 0; (2 << j) <= n; j++) {
+ for (int i = 0; i + (2 << j) <= n; i++) {
st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]);
}}}
diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp
new file mode 100644
index 0000000..31e9025
--- /dev/null
+++ b/datastructures/sparseTableDisjoint.cpp
@@ -0,0 +1,26 @@
+struct DisjointST {
+ static constexpr ll neutral = 0
+ vector<vector<ll>> dst;
+ ll* a;
+
+ ll combine(const ll& x, const ll& y) {
+ return x + y;
+ }
+
+ void init(vector<ll> *vec) {
+ int n = sz(*vec);
+ a = vec->data();
+ dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral));
+ for (int h = 0, l = 1; l <= n; h++, l *= 2) {
+ for (int c = l; c < n + l; c += 2 * l) {
+ for (int i = c; i < min(n, c + l); i++)
+ dst[h][i + 1] = combine(dst[h][i], vec->at(i));
+ for (int i = min(n, c); i > c - l; i--)
+ dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]);
+ }}}
+
+ ll query(int l, int r) {
+ int h = __lg(l ^ r);
+ return combine(dst[h][l], dst[h][r]);
+ }
+};
diff --git a/graph/2sat.cpp b/graph/2sat.cpp
index 4e47ba0..8fb3d39 100644
--- a/graph/2sat.cpp
+++ b/graph/2sat.cpp
@@ -2,13 +2,13 @@ struct sat2 {
int n; // + scc variablen
vector<int> sol;
- sat2(int vars) : n(vars*2), adjlist(vars*2) {};
+ sat2(int vars) : n(vars*2), adj(vars*2) {};
static int var(int i) {return i << 1;} // use this!
void addImpl(int a, int b) {
- adjlist[a].push_back(b);
- adjlist[1^b].push_back(1^a);
+ 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);}
diff --git a/graph/LCA.cpp b/graph/LCA.cpp
index 027d101..7debf8f 100644
--- a/graph/LCA.cpp
+++ b/graph/LCA.cpp
@@ -1,11 +1,11 @@
-vector<vector<int>> adjlist();
+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 : adjlist[gi]) {
+ for(int gn : adj[gi]) {
initLCA(gn, d+1, c);
visited[c] = gi, depth[c] = d, c++;
}}
@@ -16,9 +16,9 @@ int getLCA(int a, int b) {
void exampleUse() {
int c = 0;
- visited = vector<int>(2*sz(adjlist));
- first = vector<int>(sz(adjlist), 2*sz(adjlist));
- depth = vector<int>(2*sz(adjlist));
+ 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/articulationPoints.cpp b/graph/articulationPoints.cpp
index fb18d36..4e3dff7 100644
--- a/graph/articulationPoints.cpp
+++ b/graph/articulationPoints.cpp
@@ -1,4 +1,4 @@
-vector<vector<edge>> adjlist;
+vector<vector<edge>> adj;
vector<int> num;
int counter, rootCount, root;
vector<bool> isArt;
@@ -7,7 +7,7 @@ vector<vector<edge>> bcc;
int dfs(int v, int parent = -1) {
int me = num[v] = ++counter, top = me;
- for (edge& e : adjlist[v]) {
+ for (edge& e : adj[v]) {
if (e.id == parent){}
else if (num[e.to]) {
top = min(top, num[e.to]);
@@ -31,12 +31,12 @@ int dfs(int v, int parent = -1) {
void find() {
counter = 0;
- num.assign(sz(adjlist), 0);
- isArt.assign(sz(adjlist), false);
+ num.assign(sz(adj), 0);
+ isArt.assign(sz(adj), false);
bridges.clear();
st.clear();
bcc.clear();
- for (int v = 0; v < sz(adjlist); v++) {
+ for (int v = 0; v < sz(adj); v++) {
if (!num[v]) {
root = v;
rootCount = 0;
diff --git a/graph/blossom.cpp b/graph/blossom.cpp
index 13a3246..dd9d000 100644
--- a/graph/blossom.cpp
+++ b/graph/blossom.cpp
@@ -1,11 +1,11 @@
struct GM {
- vector<vector<int>> adjlist;
+ 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) : adjlist(n), pairs(n + 1, n), first(n + 1, n),
+ 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) {
@@ -32,7 +32,7 @@ struct GM {
auto h = label[r] = label[s] = {~x, y};
int join;
while (true) {
- if (s != sz(adjlist)) swap(r, s);
+ if (s != sz(adj)) swap(r, s);
r = findFirst(label[pairs[r]].first);
if (label[r] == h) {
join = r;
@@ -48,13 +48,13 @@ struct GM {
}}}
bool augment(int u) {
- label[u] = {sz(adjlist), -1};
- first[u] = sz(adjlist);
+ label[u] = {sz(adj), -1};
+ first[u] = sz(adj);
head = tail = 0;
for (que[tail++] = u; head < tail;) {
int x = que[head++];
- for (int y : adjlist[x]) {
- if (pairs[y] == sz(adjlist) && y != u) {
+ for (int y : adj[x]) {
+ if (pairs[y] == sz(adj) && y != u) {
pairs[y] = x;
rematch(x, y);
return true;
@@ -70,12 +70,12 @@ struct GM {
int match() {
int matching = head = tail = 0;
- for (int u = 0; u < sz(adjlist); u++) {
- if (pairs[u] < sz(adjlist) || !augment(u)) continue;
+ for (int u = 0; u < sz(adj); u++) {
+ if (pairs[u] < sz(adj) || !augment(u)) continue;
matching++;
for (int i = 0; i < tail; i++)
label[que[i]] = label[pairs[que[i]]] = {-1, -1};
- label[sz(adjlist)] = {-1, -1};
+ label[sz(adj)] = {-1, -1};
}
return matching;
}
diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp
index b8c747f..84af162 100644
--- a/graph/capacityScaling.cpp
+++ b/graph/capacityScaling.cpp
@@ -4,15 +4,15 @@ struct edge {
};
vector<edge> edges;
-vector<vector<int>> adjlist;
+vector<vector<int>> adj;
int s, t, dfsCounter;
vector<int> visited;
ll capacity;
void addEdge(int from, int to, ll c) {
- adjlist[from].push_back(sz(edges));
+ adj[from].push_back(sz(edges));
edges.push_back({from, to, 0, c});
- adjlist[to].push_back(sz(edges));
+ adj[to].push_back(sz(edges));
edges.push_back({to, from, 0, 0});
}
@@ -20,7 +20,7 @@ bool dfs(int x) {
if (x == t) return true;
if (visited[x] == dfsCounter) return false;
visited[x] = dfsCounter;
- for (int id : adjlist[x]) {
+ for (int id : adj[x]) {
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;
@@ -34,7 +34,7 @@ ll maxFlow(int source, int target) {
s = source;
t = target;
ll flow = 0;
- visited.assign(sz(adjlist), 0);
+ visited.assign(sz(adj), 0);
dfsCounter = 0;
while (capacity) {
while (dfsCounter++, dfs(s)) flow += capacity;
diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
index 50c9654..aa938ec 100644
--- a/graph/dijkstra.cpp
+++ b/graph/dijkstra.cpp
@@ -1,16 +1,16 @@
using path = pair<ll, int>; //dist, destination
-void dijkstra(const vector<vector<path>> &adjlist, int start) {
+void dijkstra(const vector<vector<path>>& adj, int start) {
priority_queue<path, vector<path>, greater<path>> pq;
- vector<ll> dist(sz(adjlist), INF);
- vector<int> prev(sz(adjlist), -1);
+ vector<ll> dist(sz(adj), INF);
+ vector<int> prev(sz(adj), -1);
dist[start] = 0; pq.emplace(0, start);
while (!pq.empty()) {
auto [dc, c] = pq.top(); pq.pop();
if (dc > dist[c]) continue; // WICHTIG!
- for (auto [dx, x] : adjlist[c]) {
+ for (auto [dx, x] : adj[c]) {
ll newDist = dc + dx;
if (newDist < dist[x]) {
dist[x] = newDist;
diff --git a/graph/graph.tex b/graph/graph.tex
index e299dd7..b090c3f 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -9,7 +9,7 @@
\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 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}
@@ -170,7 +170,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
\end{methods}
\begin{itemize}
- \item die ersten [0..n) Knoten in \code{adjlist} sind die linke Seite des Graphen
+ \item die ersten [0..n) Knoten in \code{adj} sind die linke Seite des Graphen
\end{itemize}
\sourcecode{graph/maxCarBiMatch.cpp}
\begin{methods}
diff --git a/graph/matching.cpp b/graph/matching.cpp
index 2deb672..613cabb 100644
--- a/graph/matching.cpp
+++ b/graph/matching.cpp
@@ -1,18 +1,18 @@
constexpr int MOD=1'000'000'007, I=10;
-vector<vector<ll>> adjlist, mat;
+vector<vector<ll>> adj, mat;
int max_matching() {
int ans = 0;
- mat.assign(sz(adjlist), {});
+ mat.assign(sz(adj), {});
for (int _ = 0; _ < I; _++) {
- for (int i = 0; i < sz(adjlist); i++) {
- mat[i].assign(sz(adjlist), 0);
- for (int j : adjlist[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];
}}}
- gauss(sz(adjlist), MOD); //LGS unten
+ gauss(sz(adj), MOD); //LGS unten
int rank = 0;
for (auto& row : mat) {
if (*min_element(all(row)) != 0) rank++;
diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp
index 0a38d84..588568b 100644
--- a/graph/maxCarBiMatch.cpp
+++ b/graph/maxCarBiMatch.cpp
@@ -1,21 +1,21 @@
-vector<vector<int>> adjlist;
+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 (auto w : adjlist[v]) if (pairs[w] < 0 || dfs(pairs[w])) {
+ for (auto w : adj[v]) if (pairs[w] < 0 || dfs(pairs[w])) {
pairs[w] = v; pairs[v] = w; return true;
}
return false;
}
int kuhn(int n) { // n = #Knoten links.
- pairs.assign(sz(adjlist), -1);
+ pairs.assign(sz(adj), -1);
int ans = 0;
// Greedy Matching. Optionale Beschleunigung.
- for (int i = 0; i < n; i++) for (auto w : adjlist[i])
+ 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) {
visited.assign(n, false);
diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp
index d6d0586..0e33ae4 100644
--- a/graph/minCostMaxFlow.cpp
+++ b/graph/minCostMaxFlow.cpp
@@ -5,7 +5,7 @@ struct MinCostFlow {
ll f, cost;
};
vector<edge> edges;
- vector<vector<int>> adjlist;
+ vector<vector<int>> adj;
vector<int> pref, con;
vector<ll> dist;
@@ -13,19 +13,19 @@ struct MinCostFlow {
ll maxflow, mincost;
MinCostFlow(int n, int source, int target) :
- adjlist(n), s(source), t(target) {};
+ adj(n), s(source), t(target) {};
void addedge(int u, int v, ll c, ll cost) {
- adjlist[u].push_back(sz(edges));
+ adj[u].push_back(sz(edges));
edges.push_back({v, c, cost});
- adjlist[v].push_back(sz(edges));
+ adj[v].push_back(sz(edges));
edges.push_back({u, 0, -cost});
}
bool SPFA() {
- pref.assign(sz(adjlist), -1);
- dist.assign(sz(adjlist), INF);
- vector<bool> inqueue(sz(adjlist));
+ pref.assign(sz(adj), -1);
+ dist.assign(sz(adj), INF);
+ vector<bool> inqueue(sz(adj));
queue<int> queue;
dist[s] = 0;
@@ -36,7 +36,7 @@ struct MinCostFlow {
while (!queue.empty()) {
int cur = queue.front(); queue.pop();
inqueue[cur] = false;
- for (int id : adjlist[cur]) {
+ for (int id : adj[cur]) {
int to = edges[id].to;
if (edges[id].f > 0 &&
dist[to] > dist[cur] + edges[id].cost) {
@@ -62,7 +62,7 @@ struct MinCostFlow {
}}
void mincostflow() {
- con.assign(sz(adjlist), 0);
+ con.assign(sz(adj), 0);
maxflow = mincost = 0;
while (SPFA()) extend();
}
diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp
index b8ec3e9..270cd35 100644
--- a/graph/pushRelabel2.cpp
+++ b/graph/pushRelabel2.cpp
@@ -6,7 +6,7 @@ struct edge {
};
vector<edge> edges;
-vector<vector<int>> adjlist, llist;
+vector<vector<int>> adj, llist;
vector<int> height, ccount, que;
vector<ll> excess;
vector<list<int>> dlist;
@@ -14,9 +14,9 @@ vector<list<int>::iterator> iter;
int highest, highestActive;
void addEdge(int from, int to, ll c) {
- adjlist[from].push_back(sz(edges));
+ adj[from].push_back(sz(edges));
edges.push_back({from, to, 0, c});
- adjlist[to].push_back(sz(edges));
+ adj[to].push_back(sz(edges));
edges.push_back({to, from, 0, 0});
}
@@ -28,7 +28,7 @@ void globalRelabel(int n, int t) {
int qh = 0, qt = 0;
for (que[qt++] = t; qh < qt;) {
int u = que[qh++], h = height[u] + 1;
- for (int id : adjlist[u]) {
+ for (int id : adj[u]) {
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;
@@ -55,7 +55,7 @@ void push(int u, int id) {
void discharge(int n, int u) {
int nh = n;
- for (int id : adjlist[u]) {
+ for (int id : adj[u]) {
if (edges[id].c - edges[id].f > 0) {
if (height[u] == height[edges[id].to] + 1) {
push(u, id);
@@ -79,7 +79,7 @@ void discharge(int n, int u) {
}}
ll maxFlow(int s, int t) {
- int n = sz(adjlist);
+ int n = sz(adj);
llist.assign(n + 1, {});
dlist.assign(n + 1, {});
highestActive = highest = 0;
@@ -94,7 +94,7 @@ ll maxFlow(int s, int t) {
excess.assign(n, 0);
excess[s] = inf;
excess[t] = -inf;
- for (int id : adjlist[s]) push(s, id);
+ for (int id : adj[s]) push(s, id);
globalRelabel(n, t);
while (highestActive >= 0) {
if (llist[highestActive].empty()) {
diff --git a/graph/pushRelabel3.cpp b/graph/pushRelabel3.cpp
index 1a0af81..3c17fcb 100644
--- a/graph/pushRelabel3.cpp
+++ b/graph/pushRelabel3.cpp
@@ -4,14 +4,14 @@ struct edge {
};
vector<edge> edges;
-vector<vector<int>> adjlist, hs;
+vector<vector<int>> adj, hs;
vector<ll> ec;
vector<int> cur, H;
void addEdge(int from, int to, ll c) {
- adjlist[from].push_back(sz(edges));
+ adj[from].push_back(sz(edges));
edges.push_back({from, to, 0, c});
- adjlist[to].push_back(sz(edges));
+ adj[to].push_back(sz(edges));
edges.push_back({to, from, 0, 0});
}
@@ -25,7 +25,7 @@ void addFlow(int id, ll f) {
}
ll maxFlow(int s, int t) {
- int n = sz(adjlist);
+ int n = sz(adj);
hs.assign(2*n, {});
ec.assign(n, 0);
cur.assign(n, 0);
@@ -34,16 +34,16 @@ ll maxFlow(int s, int t) {
ec[t] = 1;//never set t to active...
vector<int> co(2*n);
co[0] = n - 1;
- for (int id : adjlist[s]) addFlow(id, edges[id].c);
+ 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();
hs[hi].pop_back();
while (ec[u] > 0) {
- if (cur[u] == sz(adjlist[u])) {
+ if (cur[u] == sz(adj[u])) {
H[u] = 2*n;
- for (int i = 0; i < sz(adjlist[u]); i++) {
- int id = adjlist[u][i];
+ for (int i = 0; i < sz(adj[u]); i++) {
+ int id = adj[u][i];
if (edges[id].c - edges[id].f > 0 &&
H[u] > H[edges[id].to] + 1) {
H[u] = H[edges[id].to] + 1;
@@ -58,9 +58,9 @@ ll maxFlow(int s, int t) {
}}}
hi = H[u];
} else {
- auto e = edges[adjlist[u][cur[u]]];
+ auto e = edges[adj[u][cur[u]]];
if (e.c - e.f > 0 && H[u] == H[e.to] + 1) {
- addFlow(adjlist[u][cur[u]], min(ec[u], e.c - e.f));
+ addFlow(adj[u][cur[u]], min(ec[u], e.c - e.f));
} else {
cur[u]++;
}}}}}
diff --git a/graph/scc.cpp b/graph/scc.cpp
index b21d544..17f4a96 100644
--- a/graph/scc.cpp
+++ b/graph/scc.cpp
@@ -1,4 +1,4 @@
-vector<vector<int>> adjlist;
+vector<vector<int>> adj;
int counter, sccCounter;
vector<bool> inStack;
@@ -10,7 +10,7 @@ void visit(int v) {
d[v] = low[v] = counter++;
s.push_back(v); inStack[v] = true;
- for (auto u : adjlist[v]) {
+ for (auto u : adj[v]) {
if (d[u] < 0) {
visit(u);
low[v] = min(low[v], low[u]);
@@ -30,12 +30,12 @@ void visit(int v) {
}}
void scc() {
- inStack.assign(sz(adjlist), false);
- d.assign(sz(adjlist), -1);
- low.assign(sz(adjlist), -1);
- idx.assign(sz(adjlist), -1);
+ inStack.assign(sz(adj), false);
+ d.assign(sz(adj), -1);
+ low.assign(sz(adj), -1);
+ idx.assign(sz(adj), -1);
counter = sccCounter = 0;
- for (int i = 0; i < sz(adjlist); i++) {
+ for (int i = 0; i < sz(adj); i++) {
if (d[i] < 0) visit(i);
}}
diff --git a/graph/stoerWagner.cpp b/graph/stoerWagner.cpp
index 899cb3b..655f5aa 100644
--- a/graph/stoerWagner.cpp
+++ b/graph/stoerWagner.cpp
@@ -3,7 +3,7 @@ struct edge {
ll cap;
};
-vector<vector<edge>> adjlist, tmp;
+vector<vector<edge>> adj, tmp;
vector<bool> erased;
void merge(int a, int b) {
@@ -18,7 +18,7 @@ void merge(int a, int b) {
ll stoer_wagner() {
ll res = INF;
- tmp = adjlist;
+ tmp = adj;
erased.assign(sz(tmp), false);
for (int i = 1; i < sz(tmp); i++) {
int s = 0;
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:11:39 +0000