首页 > 其他 > 详细

P3469 割点的应用

时间:2019-08-26 21:15:23      阅读:145      评论:0      收藏:0      [点我收藏+]

https://www.luogu.org/problem/P3469

题目就是说封锁一个点,会导致哪些点(对)连不通;

用tarjan求割点,如果这个点是割点,那么不能通行的点对数就是(乘法法则)儿子子树大小的相乘+n-1;

如果不是割点就是n-1;

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e5+10;
int pre[maxn*2],last[maxn],other[maxn*2],l;
int n,m;
void add(int x,int y)
{
    l++;
    pre[l]=last[x];
    last[x]=l;
    other[l]=y;
}
bool vis[maxn];
long long ans[maxn];
int dfn[maxn],cnt,low[maxn],siz[maxn],fa[maxn];
void dfs(int x)
{
    dfn[x]=low[x]=++cnt;
    vis[x]=1;
    siz[x]=1;
    int ss=0;
    for(int p=last[x];p;p=pre[p])
    {
        int v=other[p];
        if(!vis[v])
        {
            fa[v]=x;
            dfs(v);
            siz[x]+=siz[v];
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]&&fa[x]!=v)//该儿子节点不能绕过这个点到达上方节点 
            {
                ans[x]+=(long long)ss*siz[v];//已经计算过的被封锁的儿子们乘上现在的 
                ss+=siz[v];//更新 
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
    ans[x]+=(long long )(n-1);
    ans[x]+=(long long )ss*(n-ss-1);//被封锁的儿子乘上没有被封锁的 
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        printf("%lld\n",ans[i]*2);//点对有序 
    }
    return 0;
}

 

P3469 割点的应用

原文:https://www.cnblogs.com/WHFF521/p/11414984.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!