The basic graph theory algorithms are summarized here: Summary of basic graph theory algorithms (shortest path, minimum spanning tree, bipartite graph)
LCA
Upward marking method
Time complexity O ( n ∗ m ) O(n*m) O(n∗m)
If the two nodes are different, move the deeper node upward until it moves to the same node, then the node is the common ancestor node.
code
//Preprocess the depth of each node and the number of the parent node of the node void dfs(int u, int father){ depth[u]=depth[father]+1; fa[u]=father; for(int i=h[u];~i;i=ne[i]){ int v=e[i]; if(v!=father) dfs(v,u); } } //Common ancestor of u and v int getlca(int u,int v){ //As long as u and v are different while(u!=v){ //Move the node with large depth upward if(depth[u]<depth[v]) v=fa[v]; else u=fa[u]; } return u; }
Multiplication method
Pretreatment O ( n l o g n ) O(nlogn) O(nlogn)

f a [ i ] [ j ] fa[i][j] fa[i][j] indicates the slave node i i i start, go up 2 j 2^j The number of the node in step 2j. If the root node has been exceeded, f a [ i ] [ k ] = 0 fa[i][k]=0 fa[i][k]=0. In particular, f a [ i ] [ 0 ] fa[i][0] fa[i][0] is i i The root node of i.

d e p t h [ i ] depth[i] depth[i] indicates depth. The depth of the root node is 1, i.e d e p t h [ r o o t ] = 1 depth[root]=1 depth[root]=1.

Sentry: if from i i i start jumping 2 j 2^j Step 2j will skip the root node, then f a [ i ] [ j ] = 0 fa[i][j]=0 fa[i][j]=0. d e p t h [ 0 ] = 0 depth[0]=0 depth[0]=0

Recurrence relation: f a [ i ] [ k ] = f a [ f a [ i ] [ k − 1 ] ] [ k − 1 ] fa[i][k]=fa[fa[i][k1]][k1] fa[i][k]=fa[fa[i][k−1]][k−1]
inquiry O ( l o g n ) O(logn) O(logn)
 Jump the two points to the same floor first
 Let the two points jump up at the same time until the next level of their nearest common ancestor
code
int ne[maxn],e[maxn],h[maxn],idx; int fa[maxn][21],dep[maxn]; int root; void bfs(){ queue<int>q; q.push(root); dep[root]=1,dep[0]=0; // Sentry depth[0] = 0: if you skip 2^j steps from i, you will skip the root node // fa[fa[j][k1]][k1] = 0 // Then Fa [i] [J] = 0 dep [Fa [i] [J] = dep [0] = 0 while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(dep[j]) continue; dep[j]=dep[t]+1; q.push(j); fa[j][0]=t; for(int k=1;k<=18;k++){ //Pay attention to the boundary fa[j][k]=fa[fa[j][k1]][k1]; } /* For example, understand how to exceed the root node Because we do not assign a value to the root node fa[1][0], then fa[1][0] = 0; 1 / \ 2 3 fa[1][0] = 0; fa[2][0] = 1; fa[2][1] = fa[fa[2][0]][0] = fa[1][0] = 0; */ } } } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int k=18;k>=0;k) if(dep[fa[x][k]]>=dep[y]) x=fa[x][k]; if(x==y) return x; for(int k=18;k>=0;k){ if(fa[x][k]!=fa[y][k]){ x=fa[x][k]; y=fa[y][k]; } } return fa[x][0]; }
Tarjan
Time complexity O ( n + m ) O(n+m) O(n+m), offline approach
thinking
In depth first traversal, nodes are divided into three categories:
 Branch being searched
 It has been traversed and traced back
 Points not yet searched
When we draw a graph, we can find that the first kind of points are like fruits hanging on a certain point. When we enumerate one point, the other point is the first kind of point, and their nearest common ancestor is the point hanging on the first kind of point
So we can search. If the marked point is the first kind of point in the search process, we can enumerate the queries about this point when tracing back. If the other point is the first kind of point, we can get the nearest common ancestor of this group of queries
If the other point is not the first type of point, it will be ignored temporarily, because our point will soon become the first type of point. At that time, we will take that point to complete the calculation of this group of queries. Finally, we will merge the current point into the parent node, and then the current point will become the second type of point. Finally, we can output it uniformly to complete the offline solution of the nearest public ancestor
code
/* In depth first traversal, all points are divided into three categories: [0] Points not yet searched [1] Branch being searched [2] It has been traversed and traced back */ void tarjan(int u){ st[u]=1; // u the lower left point of the root node on this road is used to query the set and to the root node for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(st[j]) continue; tarjan(j); p[j]=u; //After backtracking from the lower left, merge the lower left points to the root node } // For the current point u, search all queries to see whether the results can be obtained for(auto item:ask[u]){ int y=item.first,id=item.second; if(st[y]==2){ //This point has been backtracked, that is, it has been merged with the query set int anc=find(y); ans[id]=dis[u]+dis[y]dis[anc]*2; //Keep the original order output } } st[u]=2; //When the point u has been searched and needs to be traced back, mark st[u] as 2 }
Strongly connected component SCC of digraph
Strongly connected graph: given a directed graph. If there is a path from X to y and a path from y to X for any two nodes x, y in the graph, the directed graph is called "strongly connected graph".
Strongly connected component (SCC) refers to the polar connected subgraph of a strongly connected graph (with the most points).
In human words, any two points in a strongly connected component have edges. If any other point is added, it will no longer be a connected component.
In other words, for a directed graph, the strongly connected component is the graph with any two points having a path (x can reach y, y can also reach x) and containing the most points.
What is the use of strongly connected components of digraphs?
It mainly transforms a directed graph into a directed acyclic graph (topological graph, DAG) by reducing the point (reducing the strongly connected component to a point).
Tarjan
purpose
 Contraction point of a directed graph (directed graph  > directed acyclic graph)
Algorithm idea
 Add time stamp and initialize i, j marks;
 Put it into the stack and mark it;
 Ergodic neighbor
 If you haven't traversed it, tarjan again and update the minimum value low with low[j]
 If it is on the stack, update the minimum value low with dfn[j]
 Find the highest point
 Number of scc++
 Do while loop:
Take each element out of the stack; The sign is out of stack;
Which scc does the element belong to; Number of points in this scc++
Template
// tarjan algorithm for strongly connected components // Time complexity O(n+ m) void tarjan(int u){ // Initialize your own timestamp dfn[u] = low[u] = ++ timestamp; //Put the point on the stack stk[++ top] = u, in_stk[u] = true; // Traversing points connected with u for(int i = h[u]; ~i; i = ne[i]){ int j = e[i]; if(!dfn[j]){//If it has not been traversed, low[j] must have a value at this time tarjan(j); // The minimum value of the timestamp that the update u can traverse low[u] = min(low[u], low[j]); } // If the current point is in the stack // Note that the points stored in the stack may be several different branches of the tree, because there are cross edges // All the points stored in the stack are the points that have not been searched, and they are not the highest point of the strongly connected component // This indicates that the current strongly connected component has not been traversed, that is, there is a value in the stack else if(in_stk[j]) //Update the minimum time stamp that u points can reach //At this time, j is either the ancestor of u or the point of the cross edge, and the timestamp is less than u low[u] = min(low[u], dfn[j]); } // Find the highest point of the connected component if(dfn[u] == low[u]){ int y; ++ scc_cnt; // Number of strongly connected components++ do{// Take out all points of the connected component y = stk[top ]; in_stk[y] = false; id[y] = scc_cnt; // Which connected component does the marked point belong to size_scc[scc_cnt] ++; } while(y != u); } }
Examples
AcWing 1174. Popular cattle
#include<bits/stdc++.h> using namespace std; const int N = 10010, M = 50010; int n, m; int h[N], w[M], e[M], ne[M], idx; // A set of adjacency table // dfn[u] stores the timestamp of traversal to u // low[u] stores the smallest timestamp that can be traversed by traversing the subtree from U //Timestamp is the timestamp int dfn[N], low[N], timestamp; int stk[N], top; // Stack, and stack top element index bool in_stk[N]; // Is it on the stack //id[u] indicates the number of strongly connected components of u, scc_cnt represents the number of strongly connected components // size_scc[u] indicates the number of midpoint of strong connected component numbered U int id[N], scc_cnt, size_scc[N]; int dout[N];// Record the degree of each point in the new graph (that is, each connected component of the original graph) void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } void tarjan(int u){ //Timestamp of the current point dfn[u] = low[u] = ++ timestamp; // Add to stack stk[++ top] = u, in_stk[u] = true; //Traverse all adjacent points of u point for(int i = h[u]; ~i; i = ne[i]){ int j = e[i]; if(!dfn[j]){//If not traversed tarjan(j); // Traverse it low[u] = min(low[u], low[j]); } // The current point is in the stack else if(in_stk[j]) low[u] = min(low[u], dfn[j]); } if(dfn[u] == low[u]){ ++ scc_cnt; // Update the number of strongly connected components int y; do{ y = stk[ top]; //Constantly take out the elements in the stack in_stk[y] = false; id[y] = scc_cnt; //Number of connected block to which the y element belongs size_scc[scc_cnt] ++; //The number of points contained in the connected block }while(y != u); // Until y is not equal to u } } int main(){ cin >> n >> m; memset(h, 1, sizeof h); while(m ){ int a, b; cin >> a >> b; add(a, b); } for(int i = 1; i <= n; i ++){ if(!dfn[i]) tarjan(i); } // Directed acyclic graph // Count the outgoing degree of all points in the new graph for(int i = 1; i <= n; i ++){ for(int j = h[i]; ~j; j = ne[j]){ int k = e[j]; int a = id[i]; //a represents the number of the connected component where i is located int b = id[k]; // b represents the number of the connected component where k is located //If point i and point k are not in the same connected block // dout saves the degree, because this problem only needs the degree //In other topics, it may be to build edges, because here is to construct directed acyclic graphs if(a != b) dout[a] ++; // From a to b, the exit of A++ } } // Relevant parts of this topic: // zeros is the number of points with a degree of 0 in the new graph // sum indicates the number of points (the most popular cows) that meet the conditions int zeros = 0, sum = 0; for(int i = 1; i <= scc_cnt; i ++){ if(!dout[i]){ zeros ++; sum += size_scc[i]; if(zeros > 1){ sum = 0; break; } } } cout << sum << endl; }
Some conclusions
 After shrinking point, there is i i i starting points j j j end points, and then add m a x ( i , j ) max(i,j) max(i,j) edges, which can become strongly connected.
Double connected component DCC of undirected graph
classification
 Side double connected component eDCC
 Maximal connected block without bridge
 Two point connected component vDCC
 Maximal connected block without cut point
Shrink to a tree
Algorithm idea
Code edge
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 5010, M = 20010; int n, m; int h[N], e[M], ne[M], idx; int dfn[N], low[N], timestamp; int stk[N], top; int id[N], dcc_cnt; bool is_bridge[M]; int d[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void tarjan(int u, int from) { dfn[u] = low[u] = ++ timestamp; stk[ ++ top] = u; for (int i = h[u]; ~i; 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]) { ++ dcc_cnt; int y; do { y = stk[top  ]; id[y] = dcc_cnt; } while (y != u); } } int main() { cin >> n >> m; memset(h, 1, sizeof h); while (m  ) { int a, b; cin >> a >> b; add(a, b), add(b, a); } tarjan(1, 1); for (int i = 0; i < idx; i ++ ) if (is_bridge[i]) d[id[e[i]]] ++ ; int cnt = 0; for (int i = 1; i <= dcc_cnt; i ++ ) if (d[i] == 1) cnt ++ ; printf("%d\n", (cnt + 1) / 2); return 0; }
Code point
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 10010, M = 30010; int n, m; int h[N], e[M], ne[M], idx; int dfn[N], low[N], timestamp; int root, ans; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void tarjan(int u) { dfn[u] = low[u] = ++ timestamp; int cnt = 0; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); if (low[j] >= dfn[u]) cnt ++ ; } else low[u] = min(low[u], dfn[j]); } if (u != root) cnt ++ ; ans = max(ans, cnt); } int main() { while (scanf("%d%d", &n, &m), n  m) { memset(dfn, 0, sizeof dfn); memset(h, 1, sizeof h); idx = timestamp = 0; while (m  ) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b, a); } ans = 0; int cnt = 0; for (root = 0; root < n; root ++ ) if (!dfn[root]) { cnt ++ ; tarjan(root); } printf("%d\n", ans + cnt  1); } return 0; }
Some conclusions
 After shrinking, a tree is formed, and the tree has c n t cnt cnt leaf nodes, add ⌊ c n t + 1 2 ⌋ \lfloor \frac{cnt+1}{2 }\rfloor ⌊ 2cnt+1 ⌋ edges, which can make it doubly connected.
Euler path and Euler loop
Euler path: for graph G, if there is a path containing all edges in G, the path becomes an Euler path, also known as Euler path.
Euler loop: if the Euler path is a loop (you can return from the starting point to the ending point), it is called Euler loop.
Euler graph: a graph containing an Euler loop is an Euler graph.
determine
 Directed graph
 Euler path: the number of all singularity points in the graph is 0 or 2.
 Euler loop: the degrees of all points in the diagram are even.
 Undirected graph
 Euler path: the penetration of all points is equal to the exit, or there is one point where the exit is 1 greater than the penetration (starting point), one point where the penetration is 1 greater than the exit (end point), and the penetration of other points is equal to the exit.
 Euler loop: the in degree of all points is equal to the out degree.
thinking
skill
Edge transformation
The sequence number of edges in undirected graph is: 0 ∼ 2 m − 1 0\sim2m1 0 ∼ 2m − 1, and the number in the title is 1 ∼ m 1\sim m 1∼m;
Therefore, when transforming edges: 0,1 corresponds to edge 1, 2,3 corresponds to edge 2, that is, edge x corresponds to x/2+1
The even number is the positive edge and the odd number is the reverse edge. The relationship between the positive and reverse edges can be transformed by x^1;
If it is an odd number: in x^1, the number in front of X binary remains unchanged, and the last bit becomes 0, that is, x^1 =x1;
If it is an even number: in x^1, the number in front of X binary remains unchanged, and the last bit becomes 1, that is, x^1=x+1;
Search optimization
code: Decision Euler circuit
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100100, M = 400100; int h[N],e[M],ne[M],idx; int ans[N*2],cnt; bool used[M]; int din[N],dout[N]; int n,m,ver; void add(int a,int b){ e[idx] = b,ne[idx] = h[a],h[a] = idx++; } void dfs(int u){ for(int &i = h[u]; ~i; ){ if(used[i]){ //If this edge is used i = ne[i]; //Delete this edge continue; } used[i] = true; //Mark this edge as used if(ver == 1) used[i^1] = true; //If it is an undirected graph, the reverse edge of this edge should also be marked int t; if(ver == 1){ t = i/2 + 1; if(i&1) t = t; //(0,1) (2,3) (4,5) odd numbers are returned edges }else t = i+1; int j = e[i]; i = ne[i]; dfs(j); ans[cnt++] = t; } } int main() { scanf("%d%d%d",&ver,&n,&m); memset(h,1,sizeof h); for(int i = 0; i<m; i++){ int a,b; scanf("%d%d",&a,&b); add(a,b); if(ver == 1) add(b,a); //Undirected edge din[b]++, dout[a]++; } if(ver == 1){ for(int i = 1; i<=n; i++){ if(din[i]+dout[i] &1){ //The necessary and sufficient condition for an undirected graph to contain an Euler circuit is that the degree of each point is even puts("NO"); return 0; } } }else{ for(int i = 1; i<=n; i++){ if(din[i] != dout[i]){ //The necessary and sufficient condition for a directed graph to contain Euler circuits is that the in degree of each point is equal to the out degree puts("NO"); return 0; } } } for(int i = 1; i<=n; i++){ if(~h[i]) { dfs(i); break; } } if(cnt < m){ puts("NO"); return 0; } puts("YES"); for(int i = cnt1; i>=0; i){ cout<<ans[i]<<" "; } return 0; }
Topological sorting
purpose
 Topological sorting can determine whether there are rings in A directed graph. We can perform the above process on any directed graph and check the length of A sequence after completion. If the length of A sequence is less than the number of points in the graph, it indicates that some nodes are not traversed, and then it indicates that there are rings in the graph.
 Find topological order
thinking
Continuously select the point x with the penetration of 0, and the penetration of the point connecting x to  1.
code
void topsort(){ for(int i=1;i<=n;i++) if(!din[i]) q.push(i); while(q.size()){ int t=q.front(); q.pop(); ans[++cnt]=t; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; din[j]; if(din[j]==0) q.push(j); } } }
01 planning
Use
In graph theory problems, the following forms appear:
∑
f
(
i
)
∑
t
(
i
)
of
most
large
value
\Maximum value of frac{\sum f(i)}{\sum t(i)}
Maximum value of Σ t(i) ∑ f(i)
Consider using 01 planning
thinking
code
#include <bits/stdc++.h> #define endl "\n" #define debug(x) cout << #x << ": > " << x << endl; using namespace std; const int maxn=5e5+10; int e[maxn],ne[maxn],h[maxn],idx,wp[maxn],wseg[maxn]; double dis[maxn]; int cnt[maxn]; bool st[maxn]; int L,P; void add(int a,int b,int c){ e[idx]=b,wseg[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa(double mid){ memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); queue<int> q; for(int i=1;i<=L;i++){ q.push(i); st[i]=true; } while(q.size()){ int t=q.front(); q.pop(); st[t]=false; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; // double v=j*mid if(dis[j]<dis[t]+wp[t]mid*wseg[i]){ dis[j]=dis[t]+wp[t]mid*wseg[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=L) return true; if(!st[j]){ st[j]=true; q.push(j); } } } } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>L>>P; for(int i=1;i<=L;i++) cin>>wp[i]; memset(h,1,sizeof h); for(int i=1;i<=P;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } double l=0,r=1e7; while(rl>1e4){ double mid=(l+r)/2; if(spfa(mid)) l=mid; else r=mid; } cout<<fixed<<setprecision(2)<<l; return 0; }