圖論
連結：UVa796 Critical Links
題目：
圖，求Critical Links，指拔掉後會使原來的圖分成兩個連通塊
做法：
也就是找橋(bridge)，Tarjan
dfn&low:
- D[u]: u在dfs tree的深度
- L[u]: u點與u的子孫透過back edge連回祖先，其中深度最小的
對於圖中所有點u，若存在u的子節點v使得D[u] < L[v]，則(u,v)之間的邊為橋
code :
沒有留言:
張貼留言