P3388 【模板】割点 – tarjan

题目链接

https://www.luogu.org/problemnew/show/P3388

解题思路

tarjan求割点模板题。

什么是割点

在无向连通图中,如果将其中一个点以及所有连接该点的边去掉,图就不再连通,那么这个点就叫做割点(cut vertex / articulation point)。

怎么求割点

对于根节点,判断是不是割点很简单——计算其子树数量,如果有2棵即以上的子树,就是割点。因为如果去掉这个点,这两棵子树就不能互相到达。

对于非根节点,判断是不是割点就有些麻烦了。我们维护两个数组dfn[]和low[],dfn[u]表示顶点u第几个被(首次)访问,low[u]表示顶点u及其子树中的点,通过非父子边(回边),能够回溯到的最早的点(dfn最小)的dfn值(但不能通过连接u与其父节点的边)。对于边(u, v),如果low[v]>=dfn[u],此时u就是割点。

tarjan其他应用

tarjan还被用作求强连通分量,写法与求割点略有不同
详见https://jhcloud.top/blog/?p=1564

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=20020;

vector<int>mp[maxn];

int f[maxn],dfn[maxn],low[maxn];
int cnt;

void tarjan(int u,int o)
{
    low[u]=dfn[u]=++cnt;
    int child=0;
    for(auto v:mp[u])
    {
        if(!dfn[v])
        {
            tarjan(v,o);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=o)
            {
                f[u]=1;
            }
            if(u==o)
                child++;
        }
        low[u]=min(low[u],dfn[v]);//更新low最小
    }
    if(u==o&&child>=2)
        f[u]=1;
}

int main()
{
    ios::sync_with_stdio(false);
    cnt=0;
    int n,m;
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i,i);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(f[i])
            ans++;
    }
    cout<<ans<<endl;
    int ff=1;
    for(int i=1;i<=n;i++)
    {
        if(f[i])
        {
            if(ff)
            {
                ff=0;
                cout<<i;
            }
            else cout<<" "<<i;
        }
    }
    cout<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注