Tarjan缩点
Tarjan缩点
今天，学了tarjan缩点
要求缩点就要找强连通分量，之后就把整个图染色，把强连通分量缩成一个点，最后进行拓扑排序跑DP
强连通：如果两个顶点可以相互通达，则称两个顶点 强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。
举一个例子：
1,2,3,4就是一个强连通分量
实现
设dfn[i]表示i的dfs序
low[i]表示i只经过一条非树边到的最小的dfn
遍历一遍dfs树，求出dfn和low
答案怎么求？如果dfn[u]=low[u]代表了什么？回想一下dfn和low的定义，可以想到u这个点的子树和他是一个强连通分量。
那怎么存答案？开一个栈，遍历到的点都塞到栈里
当找到强连通分量时，把栈顶的元素一指弹，弹到u，要顺便染色。 这样就把强连通分量求出来了
在枚举每一条边，如果color[u]!=color[v]那么就说明这就是两个不同的强连通分量，重新构图，缩点就完成了。