题目: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 ;
}

最新文章

  1. 前端开发---ppt展示页面评论区支持动态交互效果
  2. JQuery之正则表达式
  3. jquery格式化时间戳 2011-01-01
  4. Android 与 Webservice 的快速保存
  5. VS2013中设置大小写的快捷键
  6. Remote Desktop manager 连接后无法自动登录
  7. mac ide
  8. 网站开发常用jQuery插件总结(15)上传插件blueimp
  9. Html代码seo优化最佳布局实例讲解
  10. 闪回工具flashback
  11. ionic3 懒加载在微信上缓存的问题
  12. cmd 配置dchp服务器
  13. hdoj4685
  14. c# AddMonths,你了解吗?
  15. linux 解压文件
  16. python 读写二进制文件实例
  17. FTP-FileZilla
  18. css属性所对应js属性
  19. 注册google账号 解决国内手机注册失败的问题
  20. C++对象的virtual table在内存中的布局

热门文章

  1. 根据table返回来的数据,动态展示组织名称
  2. leetcode-80-删除排序数组中的重复项②
  3. 【BZOJ3223】【luoguP3391】文艺平衡树
  4. 第一个duilib程序 - 实现HelloWorld详解
  5. resful风格
  6. Jeecg-Boot 2.0.1 版本发布,前后端分离快速开发平台
  7. 用Axure RP7创建响应式原型教程
  8. 解决Navicat 报错:1130-host is not allowed MySQL不允许从远程访问的方法
  9. Konig定理及证明
  10. 单例模式以及在C#中的使用