刚做了两道tarjan缩点的题，新学的算法总结一下。

推荐题：（难度单调递增）

第四题算法是tarjan+spfa求最长路，我刚刚写了一篇题解，链接在这里：

如果不会最短路点击：

总结：tarjan 简单来说 算法过程 就是找环或单独的点，这就可以构成强联通分量。

代码如下：

void tarjan(int u){    low[u]=dfn[u]=++cnt;    stk[++top]=u;    vis[u]=1;    for(register int i=head[u];i;i=edge[i].next){        int v=edge[i].to;        if(!dfn[v]){            tarjan(v);            low[u]=min(low[u],low[v]);        }        else        if(vis[v])        low[u]=min(low[u],dfn[v]);    }    if(dfn[u]==low[u]){        co[u]=++col;        vis[u]=0;        while(stk[top]!=u){        vis[stk[top]]=0;        co[stk[top]]=col;        top--;        }        top--;    }}

缩点也很简单，根据col重新建个图就行了。

 

tarjan缩点题的一些特征和突破口：

 

1.一般tarjan缩点的题会给你具有传递性的图，利用传递性可以省略掉一些点，例如：如果a喜欢b，b喜欢c，那么a就喜欢c。假设c又喜欢a，这就可以构成一个强连通分量，缩点即可，没错，这就是“受欢迎的牛”。

 

2.点的入度和出度是很重要的，很多题就围绕这这个东西去变式，关注点的入度和出度，往往会找到突破口。

 

3.有的题需要记录一些强连通分量内的数据

（1）可以在同一强连通分量中的点出栈的过程中更新，这样比较方便简单。

 

（2）也可以在主程序中再次for循环去更新，那样就比较麻烦了，时间复杂度和空间复杂度都得增加，然而我第一次打这类题就是这么操作的，代码不短。

 

反思：还是理解不够深，我的tarjan总是打错一点，然后又去修改，还是得多模拟一下tarjan缩点的过程。

 

最大的收获：发现自己tarjan一直是打错了，但是不知道为何做题却不出错，现在更改过来了。