当前位置:网站首页>【POI 2008, BLO】割点
【POI 2008, BLO】割点
2022-08-10 13:00:00 【宇智波一打七~】
题目描述
有n个点m条边无向连通图的图,保证没有重边和自环。对于每个点,输出将这个点的所有边删除之后,有多少点对不能互相连通。这里的点对是有顺序的,也就是(u,v)和(v,u)需要被统计两次。
输入格式
第一行包含两个数n,m(1≤n≤105,1≤m≤5×105)。
接下来m行,每行两个整数u,v表示一条无向边。
输出格式
n行,每行一个整数,表示答案。
样例输入
5 5
1 2
2 3
1 3
3 4
4 5
样例输出
8
8
16
14
8
思路
对于每一个点,如果这个点是割点,那么删了他之后对这个图来说是没有影响的,所以说这个点的贡献就是2*(n-1),如果这个点是割点的话,那么对于把它删去的所有连通块都乘一下就行,注意求那个割边的过程,就是如果与这个点相连的点没有返租边的话那就是割点了,下面看代码吧
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5+10;
vector<pair<int,int> > e[N];
int n,m,dfn[N],ins[N],low[N],idx,sz[N];
long long ans[N];
void dfs(int u,int id){
dfn[u] = low[u] = ++idx;
ins[u] = true;
sz[u] = 1;
ans[u] = n-1;
int cut = n-1;
for(auto pi : e[u]){
int v = pi.first,idd = pi.second;
if(!dfn[v]){
dfs(v,idd);
sz[u] += sz[v];
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u]){
ans[u] += 1ll*(n-sz[v])*sz[v];
cut -= sz[v];
}
}
else if(idd != id){
low[u] = min(low[u],dfn[v]);
}
}
ans[u] += 1ll*(cut)*(n-cut);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
e[a].pb({
b,i});e[b].pb({
a,i});
}
dfs(1,-1);
for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}
边栏推荐
- Guidelines for Sending Overseas Mail (2)
- [target detection] small script: extract training set images and labels and update the index
- ABAP file operations involved in the Chinese character set of problems and solutions for trying to read
- 日志@Slf4j介绍使用及配置等级
- 山水的高度
- 需要被记录的OpenStack相关的命令_自己用
- 【量化交易行情不够快?】一文搞定通过Win10 wsl2 +Ubuntu+redis+pickle实现股票行情极速读写
- 浙大、阿里提出DictBERT,字典描述知识增强的预训练语言模型
- 教育Codeforces轮41(额定Div。2)大肠Tufurama
- C#报错 The ‘xmins‘ attribute is not supported in this context
猜你喜欢
R语言实战应用案例:论文篇(一)-特殊柱形图绘制
来看Prada大秀吗?在元宇宙里那种!
bgp dual plane experiment routing strategy to control traffic
网络安全——XSS之被我们忽视的Cookie
11+ chrome高级调试技巧,学会效率直接提升666%
How to describe multiple paragraphs with different font settings in Open Office XML format
BEVDet4D: Exploit Temporal Cues in Multi-camera 3D Object Detection Paper Notes
ABAP file operations involved in the Chinese character set of problems and solutions for trying to read
LeetCode medium topic search of two-dimensional matrix
高数_证明_曲率公式
随机推荐
Fragment-hide and show
商汤自研机械臂,首款产品是AI下棋机器人:还请郭晶晶作代言
【百度统计】用户行为分析
[Advanced Digital IC Verification] Difference and focus analysis between SoC system verification and IP module verification
没有接班人,格力只剩“明珠精选”
Detailed explanation of es6-promise object
rpn:def concat_box_prediction_layers
Calculate the number of combinations recursively
广东10个项目入选工信部2021年物联网示范项目名单
鸿蒙开发从hello world开始
【mysql索引实现原理】
bgp双平面实验 路由策略控制流量
Import other custom namespaces in C#
BEVDet4D: Exploit Temporal Cues in Multi-camera 3D Object Detection Paper Notes
Redis 定长队列的探索和实践
【iOS】Organization of interviews
How to describe multiple paragraphs with different font settings in Open Office XML format
Borg Maze (bfs+最小生成树)
领域驱动实践总结(基本理论总结与分析V+架构分析与代码设计+具体应用设计分析)
Fragment的show和hide