P3388 【模板】割点（割顶）

本文主要是介绍P3388 【模板】割点（割顶），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

~~~~~      P3388 【模板】割点（割顶） ~~~~~      总题单链接

割点的定义

~~~~~      在一张无向图中，若删除一个点后连通块的数量会增加，那这个点就是割点。

怎么找割点

~~~~~      按 $dfs$序 访问图上的每个点，每个点只访问一遍。

~~~~~      先来看看时间戳的定义，若一个点的时间戳为 $x$，那它就是在 $dfs$ 时第 $x$ 个被访问到的点。

~~~~~      对于图上的每个点，记录 $dfn[i]$ 表示 点 $i$ 的时间戳，$low[i]$ 表示 点$i$ 在不走进入点 $i$ 的点的情况下能走到的最早时间戳。举个栗子，在 $dfs$ 的时候是从 $u$ 走到 $v$ 的，那 $low[v]$ 就是 $v$ 在不仅过过 $u$ 的情况下能走到的最早时间戳。

~~~~~      若有一条边从 $u$ 走向了 $v$，且 $low[v]>=dfn[u]$ 则这个点就是一个割点。为什么？因为 $low[v]>=dfn[u]$ 说明从 $v$ 点出发在不经过 $u$ 的情况下到不了比 $u$ 时间戳更小的点，所以这个点是割点。对这句话理解有问题的同学可以再看一看割点的定义。

割点与割边的区别

~~~~~      建议看完割边后食用。

~~~~~      若 $low[v]>=dfn[p]$ 则，这个点是割点。

~~~~~      若 $low[v]>dfn[p]$ 则，这调边是割边。

~~~~~      为什么一个是 $>=$，一个是 $>$ ，两者的区别就是能否用从 $u$ 到 $v$ 的边的反边，即从 $v$ 到 $u$ 的边来更新 $low[v]$ 。割点，割的是 $u$这个 点，所以可以用从 $u$ 到 $v$ 的边的反边来更新 $low[v]$，而割边，割的就是从 $u$ 到 $v$ 的边，自然不能用这条边的反边来更新 $low[v]$。

~~~~~      没有完全理解的同学可以再去看看割点和割边的定义。

模板题代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;vector<ll>eg[20005];
ll dfn[20005],low[20005];
ll n,m,tot,cnt,root,vis[20005];void Tarjan(ll p){dfn[p]=low[p]=++tot;ll s=0;for(ll v:eg[p]){if(!dfn[v]){Tarjan(v);low[p]=min(low[p],low[v]);if(low[v]>=dfn[p]&&!vis[p]){s++;if(p!=root||s>=2)cnt++,vis[p]=1;}}else low[p]=min(low[p],dfn[v]);}
}signed main() {ios::sync_with_stdio(false);cin>>n>>m;while(m--){ll x,y;cin>>x>>y;eg[x].push_back(y);eg[y].push_back(x);}for(ll i=1;i<=n;i++)if(!dfn[i])root=i,Tarjan(i);cout<<cnt<<endl;for(ll i=1;i<=n;i++)if(vis[i])cout<<i<<" ";return 0;
}

~~~~~      引用请附名 $——$ OMG_NOIP

这篇关于P3388 【模板】割点（割顶）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---