• 前言
• 题目大意
• 思路
  • tarjan求割点算法
• 代码
• 总结

前言

做完缩点做割点啊～

题目大意

给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

对于全部数据，$1\leq n \le 2\times 10^4$，$1\leq m \le 1 \times 10^5$。

思路

先提一下什么是割点和桥。就是本来这个图或者这个图的一部分是联通的，然后拿走了一个点，这个图就不联通了，这个被拿走的点就是一个割点。桥就是把拿走的点换成拿走的边。

tarjan求割点算法

依然是利用时间戳，$pre$ 是原本的时间戳，$low$ 是子树最低能到达的时间戳。

那么想一下，如果有一个点，它的 $low[v]\geq pre[u]$，也就是不管怎么走都只能走到 $u$ 或者是 $u$ 的子树，那么如果把 $u$ 拿掉这个就断了。

即割点存在条件为之要有任意一个符合 $low[v]\geq pre[u]$ 的点，$u$ 就是割点。

之后如果出边的点还是白点，就先递归那个点，然后用 $low[v]$ 去更新 $low[u]$。

如果不是白点，就用 $pre[v]$ 去更新 $low[u]$。

特别要注意，如果 $u$ 是根且只有一个孩子的话这个点也不是割点。

代码

#include <iostream>
using namespace std;
typedef long long ll;
const ll MAXM=2e5+5;
const ll MAXN=2e4+5;
struct edge{
    ll to,nxt;
}e[MAXM];
ll head[MAXN],tot;
void add(ll u,ll v){
    e[++tot].nxt=head[u];
    e[tot].to=v;
    head[u]=tot;
}
ll pre[MAXN],low[MAXN],dt,ans;
bool cut[MAXN];
void tarjan(ll u,ll father){
    pre[u]=low[u]=++dt;
    ll child=0;
    for (ll i = head[u]; i ; i=e[i].nxt) {
        ll v=e[i].to;
        if(pre[v]==0){
            child++;
            tarjan(v,u);
            low[u]= min(low[u],low[v]);
            if(low[v]>=pre[u]){
                cut[u]= true;
            }
        }else if(pre[v]<pre[u]&&v!=father){
            low[u]=min(low[u],pre[v]);
        }
    }
    if(father==0&&child==1){
        cut[u]= false;
    }
}
int main(){
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <=m ; ++i) {
        ll u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    for (int i = 1; i <=n ; ++i) {
        if(!pre[i]){
            tarjan(i,0);
        }
    }
    for (int i = 1; i <=n ; ++i) {
        if(cut[i]){
            ans++;
        }
    }
    printf("%lld\n",ans);
    for (int i = 1; i <=n ; ++i) {
        if(cut[i]){
            printf("%d ",i);
        }
    }
    return 0;
}

总结

学习了tarjan的割点算法