Storage of Graphs
adjacency matrix
int g[N][N];
List forward star
// Head insertion adjacency table
N Is the number of points, M Number of points
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) { // Insert an edge from a to b with a weight of c
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
int main() {
memset(h, -1 , sizeof h);
}
Storage edge
struct edge {
int a, b, c; // a points to the edge of b whose weight is c
bool const < (const& e) const { // Here, redefine the structure from small to large when sorting with the less than sign (<)
return c < e.c;
}
}edges[N];
shortest path
Naive dijkstra algorithm
time complexity is O (\ (n ^ {2} \) + m), where n represents the number of points and M represents the number of edges
int g[N][N]; // Store each edge
int dist[N]; // Store the shortest distance from point 1 to each point
bool st[N]; // Store whether the shortest circuit of each point has been determined
// Find the shortest circuit from point 1 to point n. if it does not exist, return - 1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // Find the point with the smallest distance among the points where the shortest path has not been determined
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// Update the distance of other points with t
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Heap optimized dijkstra algorithm
time complexity O(nm) n represents the number of points, and m represents the number of edges
typedef pair<int, int> PII;
int n; // Number of points
int h[N], w[N], e[N], ne[N], idx; // The adjacency table stores all edges
int dist[N]; // Store the distance from all points to point 1
bool st[N]; // Is the shortest distance to store each point determined
// Find the shortest distance from point 1 to point n. if it does not exist, return - 1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first storage distance, second storage node number
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Bellman Ford algorithm
time complexity O(nm) n represents the number of points, and m represents the number of edges
int n, m; // n represents the number of points and m represents the number of sides
int dist[N]; // dist[x] stores the shortest distance from 1 to X
struct Edge // Edge, a represents the point, b represents the entry point, and w represents the weight of the edge
{
int a, b, w;
}edges[M];
// Find the shortest distance from 1 to n. if you can't go from 1 to n, return - 1.
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// If the n-th iteration still relaxes the trigonometric inequality, it indicates that there is a shortest path with a length of n+1. According to the drawer principle, there are at least two identical points in the path, indicating that there is a negative weight loop in the graph.
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
spfa algorithm (Bellman Ford algorithm for queue optimization)
time complexity: O(m) in the average case, O (nm) in the worst case, n represents the number of points, and M represents the number of edges
when judging whether there is a negative ring, just count whether other points reaching a certain point are greater than the total points;
int n; // Total points
int h[N], w[N], e[N], ne[N], idx; // The adjacency table stores all edges
int dist[N]; // Store the shortest distance from each point to point 1
bool st[N]; // Stores whether each point is in the queue
// Find the shortest distance from point 1 to point n. if you can't walk from point 1 to point n, return - 1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // If j already exists in the queue, there is no need to insert j repeatedly
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
floyd algorithm
the time complexity is O (\ (n ^ {3} \), and N represents the number of points
initialization:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// After the algorithm, d[a][b] represents the shortest distance from a to B
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
Connected component
tarjan algorithm (strongly connected component of directed graph)
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts; // dfn records the timestamp, and low records the minimum timestamp
int stk[N], top; //
int ins[N];
int id[N], cnt;
void tarjan(int u) {
dfn[u] = low[u] = ++ ts;
stk[++ top] = u, ins[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (ins[j]) {
low[u] = min(low[u], dfn[j]);
}
}
if (dfn[u] == low[u]) {
int y;
++ cnt;
do {
y = stk[top --];
ins[y] = 0;
id[y] = cnt;
} while (y != u);
}
}
Undirected graph biconnected component
Biconnected components of edges
summary: maximal connected block without bridge
Bridge
o-o Bridge o-o
| | ↓ | |
o-o - o-o
How to find the bridge? x
/
y
x and y There is a bridge between them <=> dfn[x] < low[y] y You can't go up anyway x And low[y] = dfn[y] Namely y Is the highest point of the connected block
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts; // dfn records the timestamp, and low records the minimum timestamp
int stk[N], top;
int ins[N];
int id[N], cnt;
int is_bridge[M];
void tarjan(int u, int from) {
dfn[u] = low[u] = ++ ts;
stk[++ top] = u;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j]) {
is_bridge[i] = is_bridge[i ^ 1] = true;
}
}
else if (i != (from ^ 1)) {
low[u] = min(low[u], dfn[j]);
}
}
if (dfn[u] == low[u]) {
++ cnt;
int y;
do (
y = stk[top --];
id[y] = cnt;
)
while (y != u);
}
}
Doubly connected components of points
summary: the most common block without cut point
Cut point
o-o o-o
| \↓/ |
o-o-o-o-o
z
|
x
|
y
x Is the cut point:
low[y] <= dfn[x]
x Is the root node or x Is not a root node, but has at least two child nodes
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ts; // dfn records the timestamp, and low records the minimum timestamp
int stk[N], top;
int ins[N];
int id[N], cnt;
int is_cut[N];
void tarjan(int u) {
dfn[u] = low[u] = ++ ts;
int cnt = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
if (low[j] >= dfn[u]) {
is_cut[u] = 1;
}
}
}
}
minimum spanning tree
Undirected graph
Naive prim algorithm
the time complexity is O (\ (n ^ {2} \) + m), where n represents the number of points and M represents the number of edges
int n; // n represents the number of points
int g[N][N]; // Adjacency matrix, storing all edges
int dist[N]; // Stores the distance from other points to the current minimum spanning tree
bool st[N]; // Stores whether each point is already in the spanning tree
// If the graph is not connected, inf (the value is 0x3f3f3f3f) is returned; otherwise, the sum of tree edge weights of the minimum spanning tree is returned
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
Kruskal algorithm
the time complexity is O(mlogm), n represents the number of points, and m represents the number of edges
int n, m; // n is the number of points and m is the number of sides
int p[N]; // Parent node array of the join query set
struct Edge // Storage edge
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // Core operation of parallel query set
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // Initialize and query set
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // If two connected blocks are not connected, the two connected blocks are merged
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
Directed graph
Zhu Liu algorithm
int dnf[N], low[N], ts;
int stk[N], ins[N], top;
int id[N], cnt;
int d[N][N], bd[N][N]; // D stores the distance between two points, d[a][b] is the distance from a to B, and bd is the backup array
void tarjan(int u) {
dfn[u] = low[u] = ++ ts;
stk[++ top] = u, ins[u] = 1;
int j = pre[u];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}else if (ins[j]) low[u] = min(low[u], dfn[j]);
if (low[u] == dfn[u]) {
int y;
++ cnt;
do {
y = stk[top --];
ins[y] = 0;
id[y] = cnt;
}while (y != u);
}
}
int zhuliu() {
int ret = 0;
while (true) {
// Record the minimum entry edge of each point
for (int i = 1; i <= n; ++ i) {
pre[i] = i;
for (int j = 1; j <= n; ++ j) {
if (d[pre][i] > d[j][i]) pre[i] = j;
}
}
// Judge whether there is a ring
memset(dfn, 0, sizeof dfn)l
ts = cnt = 0;
for (int i = 1; i <= n; ++ i) {
if (!dfn[i]) tarjan(i);
}
if (cnt == n) {
for (int i = 2; i <= n; ++ i) ret += d[pre[i][i]];
break;
}
// Shrinking point
for (int i = 1; i <= cnt; ++ i) {
for (int j = 1; j <= cnt; ++ j) {
bd[i][j] = INF;
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (d[i][j] < INF && id[i] != id[j]) {
int a = id[i], b = id[j];
if (id[pre[j]] == id[j]) bd[a][b] = min(bd[a][b], d[i][j] - d[pre[j]][j]);
else bd[a][b] = min(bd[a][b], d[i][j]);
}
}
}
n = cnt;
memcpy(d, bd, sizeof bd);
}
return ret;
}
Euler path and Euler loop
necessary and sufficient conditions for the existence of Euler path:
directed graph: the exit degree of the starting point is 1 greater than the entrance degree, the end point is 1 greater than the exit degree, and the access degrees of other points are the same or all points are the same
undirected graph: there can only be 0 or 2 points with odd degrees
Hierholzer algorithm
int g[N][N];
int ans[1100], cnt;
// Starting from the starting point, each edge traversed is deleted immediately
void Hierholzer(int u)
{
for (int i = 1; i <= n; i ++ )
if (g[u][i])
{
g[u][i] --, g[i][u] -- ; // This is an undirected graph
dfs(i);
}
ans[ ++ cnt] = u;
}
existence conditions of Euler circuit:
digraph: all points have the same degree of access
undirected graph: the degrees of all points are even
int h[N], e[M], ne[M], idx;
int type, n, m;
int seq[M], cnt; // seq record Euler loop
void dfs(int u) {
for (int i = h[u]; i != -1; i = h[u]) {
if (st[i]) {
h[u] = ne[i];
continue;
}
// When type is 1, it is an undirected graph, and when type is 2, it is a directed graph
if (type == 1) st[i ^ 1] = 1; // Mark reverse edge
int t;
if (type == 1) {
t = i / 2;
if (i & 1) t = -t;
}
else t = i;
h[u] = ne[i];
dfs(e[i]);
seq[cnt ++] = t;
}
}
Network flow
Edmonds Karp algorithm
time complexity O(n\(m^{2}\)) n represents the number of points, and M represents the number of edges
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N]; // d record the flow and pre record the incoming side
int n, m, S, T;//
bool st[N];
bool bfs()
{
int hh = 0, tt = 0;
memset(st, false, sizeof st);
q[0] = S, st[S] = true, d[S] = INF;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (!st[ver] && f[i])
{
st[ver] = true;
d[ver] = min(d[t], f[i]);
pre[ver] = i;
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}
int EK()
{
int r = 0;
while (bfs())
{
r += d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
}
return r;
}
expense flow
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N]; // d record the weight, pre record the incoming side, and incf record the maximum flow to a certain place
bool st[N];
bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[i] && d[ver] > d[t] + w[i])
{
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
void EK(int& flow, int& cost)
{
flow = cost = 0;
while (spfa())
{
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}
Dinic algorithm
int h[N], e[M], ne[M], f[M], idx;
int q[M], cur[N], d[N]; // cur current arc optimization
int n, m, S, T;
bool bfs() {
forn(i, 0, N) d[i] = -1;
int hh = 0, tt = 0;
q[tt ++] = S;
d[S] = 0;
cur[S] = h[S];
while (hh < tt) {
int t = q[hh ++];
for (int i = h[t]; i != -1; i = ne[i]) {
int ver = e[i];
if (d[ver] == -1 && f[i]) {
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[tt ++] = ver;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
int ver = e[i];
cur[u] = i;
if (d[ver] == d[u] + 1 && f[i]) {
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow = 0;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
prufer coding
summary: for a rootless tree, take out the smallest node each time, output its parent node, and delete the node;
int d[N], f[N], p[N]; // d records the degree, f records the parent node, and p records the prufer corresponding code
int n, m;
void tree2prufer() { // Tree to prufer coding
for (int i = 1; i < n; ++ i) {
cin >> f[i];
d[f[i]] ++;
}
for (int i = 0, j = 1; i < n - 2;) {
while (d[j]) ++ j;
p[i ++] = f[j ++];
while (i < n - 2 && -- d[p[i - 1]] == 0 && p[i - 1] < j) p[i ++ ] = f[p[i - 1]];
}
for (int i = 0; i < n - 2; ++ i) {
cout << p[i] << " ";
}
cout << endl;
}
void prufer2tree() { prufer Code to tree
for (int i = 1; i < n - 1; ++ i) {
cin >> p[i];
d[p[i]] ++;
}
p[n - 1] = n;
for (int i = 1, j = 1; i < n; ++ i) {
while (d[j]) ++ j;
f[j ++] = p[i];
while (i < n - 1 && -- d[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], ++ i;
}
for (int i = 1; i < n; ++ i) {
cout << f[i] << " ";
}
cout << endl;
}
Huffman coding
summary: for a pile of nodes, take out the two nodes with the smallest weight each time to form a child node, and the common parent node weight is the sum of the weights of the two nodes
Topological order
summary: search widely from the point where the penetration is 0