华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1213|回复: 1
打印 上一主题 下一主题

Tarjan 缩点里面要注意的!!

[复制链接]

1

主题

6

帖子

82

积分

注册会员

Rank: 2

积分
82
跳转到指定楼层
楼主
发表于 2020-10-25 11:05:32 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
一定要分清楚 c[x](x 所在连通块) 和 x 的区别!稍不留神就搞错了!   


比如洛谷P3387缩点这一题,后面要用到拓扑排序,统计入度的时候:  


  1. for(int x=1;x<=n;++x)
  2.          for(int i=head[x];i;i=nxt[i]){
  3.                  int y=ver[i];
  4.                  if(c[x]==c[y]) continue;
  5.                  cadd(c[x],c[y]);
  6.                  ind[c[y]]++;
  7.          }
复制代码

而不是:
  1. for(int x=1;x<=n;++x)
  2.          for(int i=head[x];i;i=nxt[i]){
  3.                  int y=ver[i];
  4.                  if(c[x]==c[y]) continue;
  5.                  cadd(c[x],c[y]);
  6.                  ind[y]++;//看这一行
  7.          }
复制代码
就因为这一个小错误
我调了两天!


回复

使用道具 举报

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
沙发
发表于 2020-10-27 15:47:56 | 只看该作者
还有第二句话  low和 dfn的区别
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-11-2 06:35 , Processed in 0.178358 second(s), 22 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表