[CC-LONCYC]Lonely Cycles

题目大意:

\(T(T\le1000)\)组数据。

给定一张简单图(不含重边与自环),图中有\(n(n\le2\times10^5)\)个节点和\(m(\sum n+m\le5\times10^6)\)条边。每个节点最多属于一个简单环。

对于每条边,求出有多少简单路径包含这条边且至多包含一条在简单环上的边。

思路:

缩点后根据是否为环上边讨论,环上边的方案数就是两边结点数之积。去掉这些环就只剩下若干棵树,可以树形DP。

源代码:

#include<stack>
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=2e5+1,M=5e6;
struct Edge2 {
int u,v,id;
};
Edge2 edge[M];
struct Edge {
int to,id;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &id) {
e[u].push_back((Edge){v,id});
e[v].push_back((Edge){u,id});
}
bool ins[N],vis[N];
std::stack<int> s;
int dfn[N],low[N],scc[N],size[N],top[N],par[N],sum[N];
int64 ans[M];
void tarjan(const int &x,const int &par) {
s.push(x);
ins[x]=true;
dfn[x]=low[x]=++dfn[0];
for(auto &j:e[x]) {
const int &y=j.to;
if(y==par) continue;
if(!dfn[y]) {
tarjan(y,x);
low[x]=std::min(low[x],low[y]);
} else if(ins[y]) {
low[x]=std::min(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]) {
scc[0]++;
int y;
do {
y=s.top();
s.pop();
ins[y]=false;
scc[y]=scc[0];
} while(y!=x);
}
}
void dfs(const int &x,const int &par) {
::par[x]=par;
size[x]=vis[x]=1;
top[x]=par?top[par]:x;
for(auto &j:e[x]) {
const int &y=j.to;
if(y==par||scc[x]==scc[y]) continue;
dfs(y,x);
size[x]+=size[y];
}
}
void dp1(const int &x) {
for(auto &j:e[x]) {
const int &y=j.to;
if(y==par[x]||top[x]!=top[y]) continue;
dp1(y);
sum[x]+=sum[y];
}
}
void dp2(const int &x) {
for(auto &j:e[x]) {
const int &y=j.to,&id=j.id;
if(y==par[x]||top[x]!=top[y]) continue;
dp2(y);
ans[id]+=(int64)(size[top[x]]-size[y])*size[y];
ans[id]+=(int64)(sum[top[x]]-sum[y])*size[y];
ans[id]+=(int64)sum[y]*(size[top[x]]-size[y]);
}
}
int main() {
for(register int T=getint();T;T--) {
const int n=getint(),m=getint();
for(register int i=0;i<m;i++) {
edge[i].u=getint();
edge[i].v=getint();
edge[i].id=i;
add_edge(edge[i].u,edge[i].v,i);
}
for(register int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i,0);
}
for(register int i=1;i<=n;i++) {
if(!vis[i]) dfs(i,0);
}
for(register int i=0;i<m;i++) {
const int &u=edge[i].u,&v=edge[i].v;
if(scc[u]!=scc[v]) continue;
ans[i]=(int64)size[top[u]]*size[top[v]];
sum[u]+=size[top[v]];
sum[v]+=size[top[u]];
}
for(register int i=1;i<=n;i++) {
if(i==top[i]) dp1(i);
}
for(register int i=1;i<=n;i++) {
if(i==top[i]) dp2(i);
}
for(register int i=0;i<m;i++) {
printf("%lld\n",ans[i]);
}
//Reset
for(register int i=1;i<=n;i++) {
e[i].clear();
}
std::fill(&sum[1],&sum[n]+1,0);
std::fill(&dfn[0],&dfn[n]+1,0);
std::fill(&ans[0],&ans[m],0);
std::fill(&vis[1],&vis[n]+1,false);
scc[0]=0;
}
return 0;
}

最新文章

  1. python之元编程(元类实例)
  2. coreData数据操作
  3. GY编辑平台产品总结
  4. JqueryUI学习笔记-自动完成autocomplete
  5. nova help network-create
  6. CXF超时设置
  7. SecondarySort 原理
  8. 游戏算法中lua脚本详解
  9. Java-JMS Bug记录
  10. laravel and lumen 软删除操作
  11. 【LeetCode】476. Number Complement (java实现)
  12. 加深try catch Finnly的理解
  13. python 全栈开发,Day6
  14. Python 中@property的用法
  15. [转帖]SAP BASIS日常需要做的工作
  16. IDEAL字体颜色修改
  17. No bean named &#39;dataSource&#39; is defined
  18. js高级:event,事件冒泡,事件捕获
  19. 继承&amp;派生 属性查找
  20. RWA风险加权资产

热门文章

  1. linux关机时候执行命令脚本或程序
  2. mysql系列五、mysql中having的用法
  3. mysql系列三、mysql开启缓存、设置缓存大小、缓存过期机制
  4. composer安装laravel框架时未生成Vendor解决办法
  5. Eclipse开发时出现HTTP 403 错误(禁止访问)的解决方法
  6. impress.js
  7. gt_argmax_overlaps = overlaps.argmax(axis=0) ValueError: attempt to get argmax of an empty sequence错误处理
  8. &lt;a&gt;标签缺少href 属性,鼠标经过不会出现手型
  9. python算法双指针问题:两个有序数组的合并
  10. 开始写博客,学习Linq(5)