文章目录 割点(无向图).总结：割点算法实现模拟题解思考再来一题
割点(无向图).
P3388 【模板】割点（割顶）题目链接:洛谷
tarjan遍历过程视频链接
1.图用dfs的遍历。dfs对图，就会形成树 (写dfs代码时刻要有"栈"的思想)
2.Tarjan算法求非强连通图，主要用到了两个数组，dfn和low数组。
3.在dfs中如何加东西：
dfs（i）后面语句怎么写？每次dfs完成后，就是对前面的影响，
像栈一样。
4.无向图实际是 在无向树的基础上节点添加边。
连通图定义：
在无向图中，一个连通图中任意两点均可到达，称为连通图。
割点的定义：
在一个无向图里，去掉一个顶点，及其去掉该点的所有边,剩下的图
不连通，那么这个点就是个割点。
割边的定义： （不会不会，以后再补 。）
在一个无向图里，去掉一条边，图就不连通了。
举个栗子：下图的无向图的割点为：0,3。
ps：以下两图来自上文视频链接截下来的图。
在下图 上面数字dfn数组，下面数字low数组。
用了一个栈更好理解。
其中满足low[u]=dfn[u]，退栈到u.
dfn中是时间戳是，1-2-3-4
然后回退到2 ， 2-5
再回退到1， 1到6.
最后回退到1.结束。
强连通分量怎么就有了呢?
在退栈2时，进栈5，判断1时，low[5]=dfn[1];
之后在5中退出。
有个5-1，形成了一个1-2-5-1的环，这不就成了一个强连通分量了。
之后就是这么执行。
下面图举例（方便理解后续的代码）： 我画成树的样子，再在节点随意连，就成了无向图。
1号是该的根节点 ：那么子节点是两个， 就不是三个了？
为什么呢？
原因是： 我们在遍历的时候深度搜索，搜到3时，3就搜到4,4被标记了，退回到1节点，4节点已经标记了，1节点就不会对4搜。
所以1节点的子节点是2个。
所以只要根节点的子节点有两个及以上，根节点就是割点。（这里的子节点要细心些）。
样例输入：
上图。
题解代码如下
代码如下：
割点针对无向图！！
思考一下没s.insert(u),u会不会被重复的添加呢？
没错，当然会重复咯，不然为啥用set集合呢!，是吧 。
改一下tarjan函数
如下：
那就用ans数组记录下每个割点加了几次。
ans数组结果如下 2 1 2 2 1 2
咦！！！！细心的你发现了，咋就1加了两次呢？？？
原来顶点1是树的根呀（dfs嘛，就是图的遍历，那就树咯），1都是根了，就没有父节点。low[1]=dfn[1]=1; 所以会加一次。
这就是为啥在题解代码里会有对根节点的特判。
那么根节点怎么才能是割点呢。问到点子上了。
2020小米选拔赛第一场D题:Router Mesh
题意:
无向图n点m边
删除任意一点后，有多少个连通图
思路：
首先得知道图不一定是连通的喔。就会牵扯到有好几个连通图。
上文也讲到了ans数组。
cdxz，派上用场啦 . . . . . . ...... ......
删除一点，那他的所有边也会被删掉。那会增加几个连通图呢？？
那不得增加ans[i]个咯。
题解代码如下：
#include<iostream>#include<vector>#include<set>using namespace std;int read(){ int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar(); return s * f;}const int maxn=4e5+3;int low[maxn],dfn[maxn];int visit[maxn];int index;vector<int> a[maxn];int fa[maxn];set<int> s; int ans[maxn];inline void tarjan(int u){int sum=0;int num=0;visit[u]=1;dfn[u]=low[u]=++index;for(int i=0;i<a[u].size();i++){int v=a[u][i];if(!visit[v]){//删去了对根节点的特判，根节点会进入s集合里，如果他不是割点就只进一次。fa[v]=u;sum++;tarjan(v);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]) {num++;s.insert(u);}} else //if(v!=fa[u]) low[u]=min(low[u],dfn[v]);}//if(fa[u]==u&&sum>=2) {num++;s.insert(u);}//为啥要在这样还要num++呢，嗯。。。玄学。if(fa[u]!=u) num++;//if(u==1) cout<<num<<endl;ans[u]=num;}int main (){int n,m;n=read();m=read();int u,v;for(int i=1;i<=m;i++){u=read();v=read();a[u].push_back(v);a[v].push_back(u);}int num=0;for(int i=1;i<=n;i++){if(!visit[i]){num++;fa[i]=i;tarjan(i);index=0;}}/*cout<<s.size()<<endl;for(set<int>::iterator i=s.begin();i!=s.end();i++){cout<<*i<<" ";}*///cout<<num<<endl;for(int i=1;i<=n;i++){//在这里ans[i]减了1 //对应了这条代码if(fa[u]!=u) num++;//也就是根节点不加，非根节点要加1。cout<<ans[i]-1+num<<" ";}return 0;}