Tarjan+缩点学习笔记 - 好文

终于完成了Tarjan及缩点的学习，缩点是自己学的，花了不少精力去找好的资料，当然还是十分感谢@Menci前辈，他的笔记使我对Tarjan有了深刻理解（差不多吧，也不算多深刻，逃）。

首先，我们来讨论Tarjan算法。Tarjan是干什么的?这个问题可能看上去有些愚蠢，但是它是十分必要的。学一个算法，首先应当知道它的使用范围，尤其是名字不那么容易看出来是干什么的算法，例如：莫队算法（萌新（就是我）：什么玩意？队列吗？那加个“莫”干啥？有病吧！
大佬（SDSY某著（qi）名（pa）出题人）：那是区间操作的高效算法）。经过简要的理解，Tarjan就是求出强连通分量的一个算法，强连通不懂？请读者自行查阅资料（度娘可信）。

至于Tarjan的基本原理，我觉得这篇文章讲得很好，拉个链接过来：戳这里学习
<https://blog.csdn.net/sentimental_dog/article/details/53790582>。（特别感谢
sentimental_dog <https://blog.csdn.net/sentimental_dog>
）我就不做过多的讲解，不过提醒各位萌新在学习时一定要跟着算法流程以及示意图仔细模拟一遍，加深理解。

现在说一说缩点，其实就是拿着邻接表，和强连通分量们来建一张新的图，在新的图中，点就是原来的强连通分量，边的具体操作有点复杂，现在具体说一说，大致意思就是：既然点都变成了强连通分量，那么边就应该在他们当中去连接不是吗?那什么和什么连？似乎可以看到，连接同一个强连通分量里的点是没有任何意义的，所以就好办了，跑一遍原邻接表，如果一条边（u，v,w）的u和v不在同一个强连通分量中，那么就在新图中连这条边，就这样点就缩好了。听起来也许有些玄幻，但是它就真真切切的完成了？！

这里附上一段所缩点的代码，当然代码风格的问题自行搞定，只要你理解了邻接表就行。（Vector党请自便）
for(int i=1;i<=n;i++) for(int j=first[i];j;j=next[j])
if(sccno[i]!=sccno[e[j].v]) AddEdge2(sccno[i],sccno[e[j].v]);
就是这样，解释一下sccno[i]就是强连通分量的编号。

就讲到这里吧qwq。

热门工具换一换