bzoj1123 割点性质应用

时间:2022-09-29 16:24:50

删掉无向图上任意一点,请求出将会增加的不连通的点对数

将无向图联通性的问题转化到搜索树方向上考虑

如果一个点不是割点,那么删掉该点的答案很简单,就是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 割点性质应用的更多相关文章

  1. 洛谷 P3388 割点&lpar;割顶&rpar; 题解

    题面:     割点性质:     节点 u 如果是割点,当且仅当存在 u 的一个子树,子树中没有连向 u 的祖先的边(返祖边).     换句话说,如果对于一个点u,它的子节点是v,如果low[v] ...

  2. 【bzoj1123】【&lbrack;POI2008&rsqb;BLO】tarjan判割点

    (上不了p站我要死了,侵权度娘背锅) Description Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有t ...

  3. bzoj1123 &lbrack;POI2008&rsqb;BLO——求割点子树相乘

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1123 思路倒是有的,不就是个乘法原理吗,可是不会写...代码能力... 写了一堆麻麻烦烦乱七 ...

  4. BZOJ1123 &lbrack;POI2008&rsqb;BLO&lpar;割点判断 &plus; 点双联通缩点size&rpar;

    #include <iostream> #include <cstring> #include <cstdio> using namespace std; type ...

  5. tarjan算法与无向图的连通性&lpar;割点,桥,双连通分量,缩点&rpar;

    基本概念 给定无向连通图G = (V, E)割点:对于x∈V,从图中删去节点x以及所有与x关联的边之后,G分裂为两个或两个以上不相连的子图,则称x为割点割边(桥)若对于e∈E,从图中删去边e之后,G分 ...

  6. &lbrace;part1&rcub;DFN&plus;LOW(tarjan)割点

    什么是jarjan? 1)求割点 定义:在无向连通图中,如果去掉一个点/边,剩下的点之间不连通,那么这个点/边就被称为割点/边(或割顶/桥). 意义:由于割点和割边涉及到图的连通性,所以快速地求出割点 ...

  7. Tarjan求强连通分量,缩点,割点

    Tarjan算法是由美国著名计算机专家发明的,其主要特点就是可以求强连通分量和缩点·割点. 而强联通分量便是在一个图中如果有一个子图,且这个子图中所有的点都可以相互到达,这个子图便是一个强连通分量,并 ...

  8. Tarjan算法打包总结(求强连通分量、割点和Tarjan-LCA)

    目录 Tarjan打包总结(求强连通分量.割点和Tarjan-LCA) 强连通分量&缩点 原理 伪代码 板子(C++) 割点 原理 伪代码 最近公共祖先(LCA) 原理 伪代码 板子 Tarj ...

  9. Tarjan的缩点&amp&semi;&amp&semi;割点概述

    What is Tarjan? Tarjan,是一种用来解决图的联通性的一种有效途径,它的一般俗称叫做:缩点.我们首先来设想一下: 如果我们有一个图,其中A,B,C构成一个环,那么我们在某种条件下,如 ...

随机推荐

  1. 高效而稳定的企业级&period;NET Office 组件Spire(&period;NET组件介绍之二)

    在项目开发中,尤其是企业的业务系统中,对文档的操作是非常多的,有时几乎给人一种错觉的是”这个系统似乎就是专门操作文档的“.毕竟现在的很多办公中大都是在PC端操作文档等软件,在这些庞大而繁重的业务中,单 ...

  2. 封装js千分位加逗号和删除逗号

    //封装js千分位加逗号和删除逗号 alert( format(2545678754.020001) ) //2,545,678,754.03 alert( format(-2545678754.02 ...

  3. 6、plsql编程

    一.PLSQL编程思维导图 二.PLSQL编程思维导图对应笔记 PL/SQL编程 @Holly老师 5.1 为什么学习PL/SQL编程? 当我们要批量插入100万数据,怎么办? .难道要写一百条ins ...

  4. js原生设计模式——2面向对象编程之继承—原型继承&lpar;类式继承的封装&rpar;

    <!DOCTYPE html><html lang="en"><head>    <meta charset="UTF-8&qu ...

  5. 【机器学习基础】对 softmax 和 cross-entropy 求导

    目录 符号定义 对 softmax 求导 对 cross-entropy 求导 对 softmax 和 cross-entropy 一起求导 References 在论文中看到对 softmax 和 ...

  6. CentOS 6&period;5 x64相关安全,优化配置

    一.安全 1.修改密码长度: [root@CentOS64 ~]# vi /etc/login.defs PASS_MAX_DAYS 99999   //用户的密密码最长使用天数 PASS_MIN_D ...

  7. 查询表DML和DDL操作的最后时间

    查询test表DML操作的最后时间的语句: select max(ora_rowscn),to_char(scn_to_timestamp(max(ora_rowscn)),'yyyy-mm-dd h ...

  8. Liferay平台开发使用详细PPT演示文稿

    主要章节: 概述 功能和使用 开发扩展 安全.认证 高可用 Demo 独立流程演示工程: Liferay集成Activiti开发工程: PPT演示文稿下载 Demo程序分2部分: 独立流程演示工程:h ...

  9. 关于elk中filebeat定义好日志输出,但是redis里面却没有输出内容的问题

    这两天在搞elk的时候,filebeat中指定输出日志至Broker(此处Broker采用redis作为缓存),但是redis中却没有内容,所以就开始排查来 filebeat采用RPM安装的方式来的. ...

  10. JVM 统计监测命令

    参考 深入理解JVM(七)——性能监控工具 JVM性能调优监控工具专题一 JVM调优总结 + jstat 分析 1. 进入 jdk 目录 cd /usr/local/jdk/bin 2. 查询所有 j ...