Tarjan 缩点里面要注意的！！

Charleyxiao

一定要分清楚 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

还有第二句话  low和 dfn的区别