catalog:
Introduction cut point:
Cut point set:
In an undirected graph, if there is a vertex set, after deleting the vertex set and the edges associated with all vertices in the set, the connected component of the graph increases, this point set is called cut point set.
In undirected graph G = (V, In E): If for x ∈ V, after deleting node x and all edges associated with x from the graph, If G splits into two or more disjointed subgraphs, x is called the cut point of G. In short, a cut point is a special point in an undirected connected graph. After deleting this point, the graph is no longer connected, so the set of points that meet this condition is the cut point set.
Cut point:
If a set of cut points contains only one vertex X (that is, {X} is a set of cut points), then X is called a cut point.
Let G be a graph and X be an edge of G. if the number of connected branches of G - x is greater than the number of connected branches of G, X is said to be a bridge or edge of G.
realization:
Introduce an example: Luogu P3388 [template] cutting point (cutting top)
Obviously, for the board problem of cutting points, consider two methods (this konjac is to write violence QwQ first).
1. Violence:
As we all know, violence and enumeration or explosive search. For cut points, writing violence must write enumeration. Delete any point in each enumeration to see whether it is connected. However, for this advanced algorithm, it is obvious that enumeration will TLE .
2.Tarjan:
Next, it's the protagonist of today - Tarjan algorithm (note that another algorithm for finding connected components is also called Tarjan algorithm, which is similar to this algorithm). (Tarjan, full name Robert Tarjan, American computer scientist.)
First, select a root node and traverse the whole graph from the root node (using DFS).
For the root node, it is easy to judge whether it is a cut point - calculate the number of subtrees. If there are more than two subtrees, it is a cut point. Because if this point is removed, the two subtrees cannot reach each other.
For non root nodes, it is troublesome to judge whether it is a cut point. We maintain two arrays dfn [] and low [], dfn[u] indicates the number of vertices u are accessed (for the first time), and low[u] indicates the dfn value of the earliest point (the smallest dfn) that can be traced back through the non parent-child edge (back edge) (but not through the edge connecting u and its parent node). For the edge (u, to), if low [to] > = dfn[u], then u is the cut point.
But there is also a problem: how to calculate low[u].
Assuming that the current vertex is u, the default is low[u]=dfn[u], that is, it can only be traced back to itself at the earliest.
There is an edge (u, to). If v has not been accessed, continue DFS. After DFS, low[u]=min(low[u], low[to]);
If to has visited (and u is not the father of to), there is no need to continue DFS. There must be DFN [v] < DFN [u], low[u]=min(low[u], dfn[v]).
[code implementation]
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
struct node//Chained forward star storage graph
{
int to;
int nex;
}mapp[200010];
int n,m,a,b,sum;
int head[100010],tot;
int dfn[100010],cnt;
int low[100010];
bool vis[100010];
void add(int x,int y)//Add edges (x,y) to the graph
{
mapp[++tot]=(node){y,head[x]};
head[x]=tot;
return;
}
void tarjan(int u,int fa)//tarjan finding cut point
{
dfn[u]=low[u]=++cnt;//initial
int son=0;//Used to count the number of subtrees
for(int i=head[u];i;i=mapp[i].nex)
{
int to=mapp[i].to;
if (!dfn[to])
{
tarjan(to,fa);
low[u]=min(low[u],low[to]);
if(low[to]>=dfn[u]&&u!=fa) vis[u]=1;
if(u==fa) son++;
}
low[u]=min(low[u],dfn[to]);
}
if(son>=2&&u==fa) vis[u]=1;
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {scanf("%d%d",&a,&b);add(a,b);add(b,a);}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
for(int i=1;i<=n;i++) if(vis[i]) sum++;//Statistical cut points
printf("%d\n",sum);
for(int i=1;i<=n;i++) if(vis[i]) printf ("%d ",i);//output
return 0;//Sprinkle flowers at the end
}Another template question!!!
