tarjan缩点（洛谷P387)
- 2019 年 10 月 3 日
- 笔记
此题解部分借鉴于九野的博客
题目分析
- 给定一个 (n) 个点 (m) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
-
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
-
假如没有后面这条限制的话,那图一定是一个无环图。因为有环的话我可以一直在环上跑，所以答案就没有一个上界
-
没有环的话我萌可以很自然地想到一个 (O(n)) 的 拓扑(dp) 做法，先做入度为 (0) 的点，更新入度不为 (0) 的点，把更新后入度为 (0) 的点加入队列里，继续做之前的事情
-
现在考虑有环怎么做
-
有一个贪心的思路是，到环上就先把环上的点都走完，再从环上任意一点出发
-
其实这个环可以看做一个大点，也就是我们今天要介绍的主角 (to) 缩点
tarjan缩点
下面这张图是从 九野的博客 那 copy 过来的
- 把可以互相抵达的点集叫做一个连通分量
- 最大的那个可以互相抵达的点点集即为强连通分量
- 特别的，单个的点也可以是强连通分量
比如说 ：({ 4, 5 }) 是一个联通分量，而 ${4,5,6 } $ 则是一个强连通分量（一个大点）
tarjan的过程就是通过 dfs 找强连通分量（大点）的过程
对图dfs一下，遍历所有未遍历过的点 ，会得到一个有向树，显然有向树是没有环的。（注意搜过的点不会再搜
则能产生环的 只有（指向已经遍历过的点）的边
我们发现 (7 to 3) （红边 / 横叉边）这种边一定不会产生连通分量
而 (6 to 4) （绿边 / 返祖边）这种边一定会产生联通分量
具体来说：具有父子关系的边一定会产生联通分量
我们在dfs的时候需要用一个栈来保存当前所在路径上的点（栈中所有点一定是有父子关系的）
我们用一些数组来表示dfs的过程
int tim, dfn[MAX], low[MAX](dfn[i]) 表示遍历到节点 (i) 的时间戳（第几次遍历）
(low[i]) 表示往上可以到达最早的点
初始化 (dfn[i] = low[i] = ++tim)
我们可以根据上面过程的步骤写出以下代码
for(int i = head[u]; i; i = nex[i]) { if(dfn[to[i]]) { if(instack[to[i]]) { if(low[to[i]] < low[u]) { low[u] = low[to[i]]; } } } else { dfs(to[i]); if(low[to[i]] < low[u]) {} low[u] = low[to[i]]; } } }假如当前节点 (u)， (dfn[u] == low[u]) 那就说明栈顶元素一直到节点 (u) 都属于一个强联通分量，感性理解
把栈中元素弹出并且把他们都给标记为同一种颜色（同一个强连通分量）
if(dfn[u] == low[u]) { ++totcol; do { int v = stk[top]; col[v] = totcol; instack[v] = false; } while(stk[top--] != u); }具体实现看代码
这里还有一道 tarjan练手好题
