版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41603898/article/details/102146708
题意:有n个点m条无向边,每个点要拜访其他所有点,总共有n*(n-1)次拜访次数。保证图联通,问禁止通行某个点后一共会少多少次拜访次数。输出n行,每行代表 i点禁止通行会减少的拜访次数。
解:如果这个点不影响图的联通性,则答案为2*(n-1),也即他不能到所有的n-1个点,n-1个点也不能到达他。
如果影响图的联通性,也就是割点,则答案再加上各个分量累乘之和,采用tarjan求割点时,由于是像树一样遍历,考虑子树之间对答案的贡献和所有子树之和对除子树外的点的贡献。求出的是单向的输出*2
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100005;
int n,m,x,y,tot,tim;
int dfn[N],low[N],size[N],head[N],cut_point[N];
ll ans[N];
struct Edge{
int to,nxt;
}edge[1000005];
void add(int x,int y){
tot++;
edge[tot].to = y;
edge[tot].nxt = head[x];
head[x] = tot;
}
int tarjan(int now){
int z = 0;size[now] = 1;
dfn[now] = low[now] = ++tim;
for(int i=head[now];i;i=edge[i].nxt){
int t = edge[i].to;
if(!dfn[t]){
tarjan(t);
size[now]+=size[t];
low[now] = min(low[now],low[t]);
if(dfn[now]<=low[t]){
ans[now]+=(ll)z*size[t];
z+=size[t];
}
}else low[now] = min(low[now],dfn[t]);
}
ans[now]+=(ll)z*(n-z-1);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
tarjan(1);
for(int i=1;i<=n;i++){
printf("%lld\n",(ans[i]+n-1)<<1);
}
return 0;
}