依旧不会，依旧问AI
Tarjan算法有着多种多样的应用。最出名的当属桥，割点，有向图的强连通分量。今天我们来说说割点，剩下的以后有时间再另发文章。
具体题目见洛谷割点模板题
**割点就是能把一个连通的图切割成两个独立的图。**那我们如何才能找到割点呢？可以分两种情况讨论。想象一个树状图，如果root有两个分支及以上的话，我们就可以把root去掉。太好了！我们成功的把一个树变成了两个树！但是，这有一个前提。下面的左右两个树不能有一个小路连接，这可怎么办呢？只能判断了。我们把左边和右边都深度搜索一下，如果有小路，左边的数字就会把右边的树也给统统标记。也就是说，咱们在root上时，可以利用左边的数来把右边的树也给染上数字，再来看看右边树上离root最近的点有没有被染上“数”就行了。
第二种情况也较为复杂。我们要继续分类讨论了! （不想打字了QwQ ） 依旧想想一条笔直的树。比如1 – 2 – 3 – 4 – 5。我们就三而言讨论一下。如果只是这样的话，我们直接把三断掉，就可以分成两半了。可惜，不知是谁把5与其他的点修了一条路（肯定不是我 ）。假设5与4连接了起来，我们继续把三断掉，没有问题，又分成了两份。5与3连接了起来，没关系，我们把3这一整个城市摧毁，依旧无法到2，可分成两份。但是我把2与5连接了起来（就问你气不气 ）。我把三断掉时，怎么还连着！气死我了！那三就不是割点了QwQ。
好了！我们就把情况都讨论完了！简单不！
接下来就是实现代码了。我们要用low和dfn两个数组来实现代码。 提示：要用一个father数来提醒这个点不要回到原来的点。其次，要有一个数来记住每个点有多少个儿子。最后，我们可以把low当成一个类似标记数组的东西，确定这个点属于哪个图中。用这个low数组与其他点打擂台，把他们也给拉拢进自己的家族中，并告诉他们老大是谁，是他们的low数组也变成老大的名字。dfn就是每个点的名字。
好了，不多说了，直接给AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int n,m,x,y,cnt;
priority_queue<int,vector<int> , greater<int> > point;
vector<int> g[N];
int dfn[N],low[N];
int ptf[N];
int root;
int result;
void Tarjan(int num,int fa){
int child=0;
cnt++;
dfn[num]=cnt;
low[num]=cnt;
for(int i=0;i<g[num].size();i++){
int v=g[num][i];
if(fa==g[num][i]) continue;
if(dfn[v]==0){
child++;
Tarjan(v,num);
low[num]=min(low[v],low[num]);
if(root!=num&&ptf[num]==0&&dfn[num]<=low[v]){
result++;
point.push(num);
ptf[num]=1;
}
}else{
low[num]=min(low[num],dfn[v]);
}
}
if(num==root&&child>=2&&ptf[num]==0){
result++;
point.push(num);
ptf[num]=1;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(dfn[i]==0){
root=i;
Tarjan(i,–1);
}
}
cout<<result<<"\\n";
while(!point.empty()){
int ans=point.top();
point.pop();
cout<<ans<<" ";
}
return 0;
}
点个赞吧，还有收藏！球球了QwQ
