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練手好題
