华师一附中OI组

标题: Tarjan 缩点里面要注意的！！ [打印本页]

---

作者: Charleyxiao    时间: 2020-10-25 11:05
标题: Tarjan 缩点里面要注意的！！
一定要分清楚 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.          }

复制代码

就因为这一个小错误
我调了两天！

---

作者: admin    时间: 2020-10-27 15:47
还有第二句话  low和 dfn的区别

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2