tarjan2
反過來調過去，我還是感覺沒學明白縮點
- 講一個有向圖中的所有強連通分量縮成一個點後，構成的新圖是一個DAG。
- 一個點所在的強連通分量一定被該點所在DFS搜索樹所包含
- 樹上的邊大致分為：樹枝邊，前向邊（從上往下指），後向邊（從下往上指），橫叉變。其中前向邊肉眼可見地沒什麼卵用
接下來開始演算法流程。
- tarjan的精髓如上次所說，在於DFS搜索樹，在DFS搜索樹中強連通分量以怎樣形式存在是關鍵問題。對於x，存在祖宗y，從x出發可經過橫叉邊，返祖邊，後向邊到達y，則x，y屬於同一強連通分量。操作中記錄最小 y 為：low(x)=dfn(y)。（其中單點也算強連通塊）如果有一個dfn_x=low_x ，那麼就是說 x 在一個新的強連通塊里，同理，low_x的初始也就是dfn_x。
- 我們用一個棧來維護 已經被遍歷過的、還未確定隸屬哪個強連通分量的 點，在該棧中越靠棧頂DFS序越靠後（是棧底元素的後代）。
- 關於low_x的求法、更新。考慮如何求low_x：low_x 可能被更新，當且僅當x連出了一條樹枝邊，橫叉邊或後向邊。設該邊連向點 v
1. 樹枝邊： low_x= min(low_x,low_v) v 到達的點x一定可以到達，且v與x有祖宗關係
2. 後向邊： low_x= min(low_x,low_v) v 的祖先一定是 x 的祖先
3. 橫叉邊：此時分兩種情況考慮的
當 v 點已經退棧時，那麼點v可到達的DFS序最小的祖先不是x的祖先，對 low_x 沒有貢獻； 當點v還在棧中時，v 點可到達的DFS序最小的祖先是x的祖先，有 low_x=min(low_x,low_v) (點v可到達的DFS序最小的祖先一定是x的，v 點能到達的點，x一定能到達) 特別地,由於前向邊的更新對於求強連分量沒有幫(更新是重複的)，所以我們也可以有 low_x=min(low_x,low_v)
那麼我們只需判斷點 x 連出的邊是哪一條就可以轉移了。顯然,當 dfn_v=0 時（此時v未被訪問過），這是一條樹枝邊。我們再維護一個 col 數組， col_i 表示點 i 所在的強連通分量,在點 i 退棧時,我們對col進行賦值,那麼當 dfn_v≠0&&col_v=0 時,點v一定在棧中（後向邊指向的點一定在棧中,橫叉邊指向的點滿足此條件時在棧中,而前向邊是否存在與答案無關），此時用 low_x=min(low_x,low_v) 轉移即可,否則無需轉移。該演算法時間複雜度為(n+m),因為深度優先遍歷每個點只會經過一次,每條邊也只會訪問一次,而每個點都只會進/出棧一次,所以總時間複雜度為(n+m)
//把一個點當成根提溜出來，抖摟抖摟成一棵樹
void dfs(int u)
{
//記錄dfs序
//可通過任意多dfs邊與最多一條非樹返祖邊到達的、本強連通分量內最小點
dfn[u]=low[u]=++dfs_clock;
s.push(u);
for(int v:g[u])
{
if(!dfn[v])//樹邊
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!sccnum[v])//返祖
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scccnt++;//強連通塊+1
while(1)
{
int x=s.top();
s.pop();
sccnum[x]=scccnt;
sccsz[scccnt]++;
if(x==u) break;
}
}
}
