删掉无向图上任意一点,请求出将会增加的不连通的点对数
将无向图联通性的问题转化到搜索树方向上考虑
如果一个点不是割点,那么删掉该点的答案很简单,就是2*(n-1)
如果点u是割点,同时u在搜索树上有t个子节点,那么删掉u点后就会出现t+2个联通分量
1.t个包含不同子节点的联通分量:每个子节点联通分量的贡献是size[son]*(n-size[son])
2.结点u:u的贡献是(n-1)
3.剩下部分,即u子树除外其他的点形成的联通分量:这部分的贡献是n-1-sum{size[son]}
在tarjan时同时求出size数组即可
#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
struct Edge{int to,nxt;}edge[maxn<<];
int head[maxn],tot,n,m;
long long ans[maxn]; void init(){
tot=;
memset(head,-,sizeof head);
}
void addedge(int u,int v){
edge[tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot++;
} int cut[maxn],low[maxn],dfn[maxn],size[maxn],ind;
void tarjan(int u){
dfn[u]=low[u]=++ind;
size[u]=;
int flag=,sum=;
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
size[u]+=size[v];
if(low[v]>=dfn[u]){
flag++;
ans[u]+=(long long)size[v]*(n-size[v]);
sum+=size[v];
if(u!= || flag>)
cut[u]=true;//u是割点
}
}
else low[u]=min(low[u],dfn[v]);//回边
}
if(cut[u])
ans[u]+=(long long)(n-sum-)*(sum+)+(n-);//加上剩余部分
else
ans[u]=*(n-);
} int main(){
init();
cin>>n>>m;
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u==v)continue;//规定无重边
addedge(u,v);
addedge(v,u);
}
tarjan();
for(int i=;i<=n;i++)
printf("%lld\n",ans[i]); }
bzoj1123 割点性质应用的更多相关文章
-
洛谷 P3388 割点(割顶) 题解
题面: 割点性质: 节点 u 如果是割点,当且仅当存在 u 的一个子树,子树中没有连向 u 的祖先的边(返祖边). 换句话说,如果对于一个点u,它的子节点是v,如果low[v] ...
-
【bzoj1123】【[POI2008]BLO】tarjan判割点
(上不了p站我要死了,侵权度娘背锅) Description Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有t ...
-
bzoj1123 [POI2008]BLO——求割点子树相乘
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1123 思路倒是有的,不就是个乘法原理吗,可是不会写...代码能力... 写了一堆麻麻烦烦乱七 ...
-
BZOJ1123 [POI2008]BLO(割点判断 + 点双联通缩点size)
#include <iostream> #include <cstring> #include <cstdio> using namespace std; type ...
-
tarjan算法与无向图的连通性(割点,桥,双连通分量,缩点)
基本概念 给定无向连通图G = (V, E)割点:对于x∈V,从图中删去节点x以及所有与x关联的边之后,G分裂为两个或两个以上不相连的子图,则称x为割点割边(桥)若对于e∈E,从图中删去边e之后,G分 ...
-
{part1}DFN+LOW(tarjan)割点
什么是jarjan? 1)求割点 定义:在无向连通图中,如果去掉一个点/边,剩下的点之间不连通,那么这个点/边就被称为割点/边(或割顶/桥). 意义:由于割点和割边涉及到图的连通性,所以快速地求出割点 ...
-
Tarjan求强连通分量,缩点,割点
Tarjan算法是由美国著名计算机专家发明的,其主要特点就是可以求强连通分量和缩点·割点. 而强联通分量便是在一个图中如果有一个子图,且这个子图中所有的点都可以相互到达,这个子图便是一个强连通分量,并 ...
-
Tarjan算法打包总结(求强连通分量、割点和Tarjan-LCA)
目录 Tarjan打包总结(求强连通分量.割点和Tarjan-LCA) 强连通分量&缩点 原理 伪代码 板子(C++) 割点 原理 伪代码 最近公共祖先(LCA) 原理 伪代码 板子 Tarj ...
-
Tarjan的缩点&;&;割点概述
What is Tarjan? Tarjan,是一种用来解决图的联通性的一种有效途径,它的一般俗称叫做:缩点.我们首先来设想一下: 如果我们有一个图,其中A,B,C构成一个环,那么我们在某种条件下,如 ...
随机推荐
-
高效而稳定的企业级.NET Office 组件Spire(.NET组件介绍之二)
在项目开发中,尤其是企业的业务系统中,对文档的操作是非常多的,有时几乎给人一种错觉的是”这个系统似乎就是专门操作文档的“.毕竟现在的很多办公中大都是在PC端操作文档等软件,在这些庞大而繁重的业务中,单 ...
-
封装js千分位加逗号和删除逗号
//封装js千分位加逗号和删除逗号 alert( format(2545678754.020001) ) //2,545,678,754.03 alert( format(-2545678754.02 ...
-
6、plsql编程
一.PLSQL编程思维导图 二.PLSQL编程思维导图对应笔记 PL/SQL编程 @Holly老师 5.1 为什么学习PL/SQL编程? 当我们要批量插入100万数据,怎么办? .难道要写一百条ins ...
-
js原生设计模式——2面向对象编程之继承—原型继承(类式继承的封装)
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8&qu ...
-
【机器学习基础】对 softmax 和 cross-entropy 求导
目录 符号定义 对 softmax 求导 对 cross-entropy 求导 对 softmax 和 cross-entropy 一起求导 References 在论文中看到对 softmax 和 ...
-
CentOS 6.5 x64相关安全,优化配置
一.安全 1.修改密码长度: [root@CentOS64 ~]# vi /etc/login.defs PASS_MAX_DAYS 99999 //用户的密密码最长使用天数 PASS_MIN_D ...
-
查询表DML和DDL操作的最后时间
查询test表DML操作的最后时间的语句: select max(ora_rowscn),to_char(scn_to_timestamp(max(ora_rowscn)),'yyyy-mm-dd h ...
-
Liferay平台开发使用详细PPT演示文稿
主要章节: 概述 功能和使用 开发扩展 安全.认证 高可用 Demo 独立流程演示工程: Liferay集成Activiti开发工程: PPT演示文稿下载 Demo程序分2部分: 独立流程演示工程:h ...
-
关于elk中filebeat定义好日志输出,但是redis里面却没有输出内容的问题
这两天在搞elk的时候,filebeat中指定输出日志至Broker(此处Broker采用redis作为缓存),但是redis中却没有内容,所以就开始排查来 filebeat采用RPM安装的方式来的. ...
-
JVM 统计监测命令
参考 深入理解JVM(七)——性能监控工具 JVM性能调优监控工具专题一 JVM调优总结 + jstat 分析 1. 进入 jdk 目录 cd /usr/local/jdk/bin 2. 查询所有 j ...