题目链接:传送门

思路:

求割点的同时求割点删除后所剩的不连通的点的对数,在遍历完成后回溯统计点的个数,具体操作见代码;

注意:结果是long long 类型。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 1e6+;
int head[maxn],next[maxn],ver[maxn],tim;
LL size[maxn],ans[maxn];
int low[maxn],num[maxn],tot,m,n;
int MIN(int x,int y)
{
return x<y?x:y;
}
void Init()
{
memset(head,,sizeof(head));
memset(num,,sizeof(num));
memset(low,,sizeof(low));
memset(ans,,sizeof(ans));
memset(size,,sizeof(size));
tot=;tim=;
}
void addedge(int u,int v)
{
ver[++tot]=v;next[tot]=head[u];head[u]=tot;
}
void Tarjan(int u)
{
low[u]=num[u]=++tim;
size[u]=;
int i,v,cnt=;
LL tp=;
for(i=head[u];i;i=next[i]){
v=ver[i];
if(!num[v]){
cnt++;
Tarjan(v);
size[u]+=size[v]; //统计每一个相邻节点
low[u]=MIN(low[u],low[v]);
if(num[u]<=low[v]){
ans[u]+=(LL)tp*size[v]; //已知区块节点数*相邻区块的节点数
tp+=size[v];//更新已知区块
}
}
else low[u]=MIN(low[u],num[v]);
}
ans[u]+=tp*(n--tp);//因为是连通图,所以要增加除了相邻节点以外图中剩余未访问的节点的数量和
}
int main(void)
{
int i,j,x,y;
while(~scanf("%d%d",&n,&m)){
Init();
for(i=;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
Tarjan();
for(i=;i<=n;i++)
printf("%lld\n",(ans[i]+n-)*);
}
return ;
}

最新文章

  1. mysql源码包手动安装、配置以及测试(亲测可行)
  2. 开始使用 UIAlertController 吧
  3. JDK环境变量详细讲解
  4. [EmguCV|WinForm] 使用EmguCV內建直方圖工具繪製直方圖(Histogram)-直方圖(Histogram)系列 (1)
  5. 给img添加类名可以动态切换图片
  6. 当 IDENTITY_INSERT 设置为 OFF 时,不能为表中的标识列插入显式值
  7. sql语句语法大全
  8. 说说Audition消除歌曲中的人声
  9. windows装liunx双系统
  10. unity脚本的基础语法
  11. TJU 2944 Mussy Paper 最大权闭合子图
  12. 深入浅出Windows BATCH
  13. proxymysql的安装与应用
  14. WEB框架-Django框架学习(二)- 模型层
  15. 【软件安装与环境配置】TX2安装配置caffe过程
  16. suoi62 网友跳 (暴搜+dp)
  17. Guideline 5.2.1 - Legal - Intellectual Property 解决方案
  18. zookeepercli - Command Line Interface for ZooKeeper
  19. &lt;Parquet&gt;&lt;Physical Properties&gt;&lt;Best practice&gt;&lt;With impala&gt;
  20. 使用JavaScript实现简单的小游戏-贪吃蛇

热门文章

  1. logging-----日志模块
  2. ansible自动化
  3. k8s重启策略
  4. 使用c#调整图片质量
  5. pytorch之张量的理解
  6. freeswitch 使用info显示的通道变量
  7. SpringCloud Zuul网关的简单理解
  8. poj2182(线段树求序列第k小)
  9. composer的安装以及具体使用
  10. go语言环境安装