首页 技术 正文
技术 2022年11月23日
0 收藏 833 点赞 2,929 浏览 1723 个字

又可以水紫题了,好开心

前置芝士

无向图割点,然后脑子。。。

不会的童鞋,出门右转,百度百科。。。QAQ

首先,对于这道题,我们要求的是,割去每个点及他所连的边后,无向图中,有多少有序点对(\(x\),\(y\))满足

\(x\),\(y\)互不连通

我们思考一下,这道题既然跟点有关,那么我们可以想到,在无向图中,我们可以把所有的点分为两种,割点,

和非割点。

我们大力讨论一下。。。。

对于非割点

把他去掉之后,就会发生这样的事情,

样例原始图是这样

5不是割点,去掉她以及他连的边后

就会成这样

他就会与剩下\(n-1\)个点,不相连,那么他的\(ans\)就是\(2\times (n-1)\)

那么对于割点呢?????

其实不难,请同学自证

假如 \(j\) 是割点把 \(j\) 割掉后,图就会分成好几个联通快。那么求出每个连通块的大小,再分别乘起来就行。

我们把它放到搜索树上考虑,这几种连通块就会有以下几种情况

  1. 割点 \(j\) 单独成一个块。
  2. \(j\) 的每个子树都是一个连通块
  3. 除了 \(j\) 和他子树中的点,其他点构成一个连通块

就像这样

原图

5是割点

割去5后,变成这样

他的搜索树长这样

他的子树 6 ,2 , 3 各成一个联通快

它上面的 1 4 节点成一个连通块

他自己又成一个联通块

因此割点的答案就是

\(\displaystyle\sum_{k = 1}^{k}size_i\times (n-size_i)\) + (\(n\)-\(sum + 1\)) * (\(sum + 1\)) + (\(n-1\));

\(sum\) 是他子树的大小,\(n-sum+1\) 为剩下的大联通块的大小,\(sum+1\)就是他自己和他子树的大小

上代

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n,m,x,y,tot,num,root;
int head[N],dfn[N],low[N],size[N];
long long ans[N];
bool cut[N];
struct node{int to ,net;} e[500100*2];
inline int read()
{
int s = 0 , w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
void tarjain(int x)
{
dfn[x] = low[x] = ++num; size[x] = 1;
int flag = 0,sum = 0;//sum是子树和
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(!dfn[to])
{
tarjain(to);
size[x] += size[to];//统计一下他的size
low[x] = min(low[x],low[to]);
if(low[to] >= dfn[x])
{
flag++;
ans[x] += (long long) size[to] * (n - size[to]);//统计一下他子树的贡献
sum += size[to];
if(x != root || flag > 1) cut[x] = true;
}
}
else low[x] = min(low[x] , dfn[to]);
}
if(cut[x] = true) ans[x] += (long long) (n - sum - 1) * (sum + 1) + (n-1);//最后加上他的贡献和其他点的贡献
else ans[x] = 2 * (n-1);//非割点的情况
}
int main()
{
n = read(); m = read();
for(int i = 1; i <= m; i++)
{
x = read(); y = read();
add(x,y); add(y,x);
}
root = 1; tarjain(1);
for(int i = 1; i <= n; i++) printf("%lld\n" , ans[i]);
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141184.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,509
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,315
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站