bzoj 1123 [POI2008]BLO——点双连通分量
2024-10-08 00:05:12
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1123
点双连通分量缩点,然后各种各样。
结果不会写了。比如新连边、记录一个点是割点缩成的点还是一块缩成的点什么的。
然后去学习了TJ。其实根本不用把缩点后的图真的建出来嘛!而且人家写得好好!唉,代码能力?
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=1e5+,M=5e5+;
int n,m,hd[N],xnt,siz[N],dfn[N],low[N],tim;
ll ans[N];
struct Ed{
int nxt,to;Ed(int n=,int t=):nxt(n),to(t) {}
}ed[M<<];
void add(int x,int y)
{
ed[++xnt]=Ed(hd[x],y);hd[x]=xnt;
ed[++xnt]=Ed(hd[y],x);hd[y]=xnt;
}
void tarjan(int cr)
{
dfn[cr]=low[cr]=++tim;siz[cr]=;
ll t=;
for(int i=hd[cr],v;i;i=ed[i].nxt)
if(!dfn[v=ed[i].to])
{
tarjan(v);
low[cr]=min(low[cr],low[v]);siz[cr]+=siz[v];
if(low[v]>=dfn[cr])
{
ans[cr]+=t*siz[v];t+=siz[v];
}
}
else low[cr]=min(low[cr],dfn[v]);
ans[cr]+=t*(n-t-);
}
int main()
{
scanf("%d%d",&n,&m);int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);add(x,y);
}
tarjan();
for(int i=;i<=n;i++)
printf("%lld\n",(ans[i]+n-)<<);
return ;
}
最新文章
- 前端开发---ppt展示页面评论区支持动态交互效果
- JQuery之正则表达式
- jquery格式化时间戳 2011-01-01
- Android 与 Webservice 的快速保存
- VS2013中设置大小写的快捷键
- Remote Desktop manager 连接后无法自动登录
- mac ide
- 网站开发常用jQuery插件总结(15)上传插件blueimp
- Html代码seo优化最佳布局实例讲解
- 闪回工具flashback
- ionic3 懒加载在微信上缓存的问题
- cmd 配置dchp服务器
- hdoj4685
- c# AddMonths,你了解吗?
- linux 解压文件
- python 读写二进制文件实例
- FTP-FileZilla
- css属性所对应js属性
- 注册google账号 解决国内手机注册失败的问题
- C++对象的virtual table在内存中的布局