UVa315 Network

成大最近在上圖論～

認真寫習題> <

連結：UVa315 Network

題目：

給一張圖，求出圖中有幾個關節點(Articulation Point)

做法：

圖論的基本介紹可以看：建中培訓講義

dfn&low:

• D[u]: u在dfs tree的深度
• L[u]: u點與u的子孫透過back edge連回祖先，其中深度最小的

判斷u點是否為Articulation Point(AP)

1. 若u為根節點，則當u有兩顆或以上的子樹時，u為AP，當u被切除後子樹間無法連通
2. 若u非根節點，當任一子節點v滿足L[v] >= D[u]，u為AP，當u被切除後該子樹無法與祖先連通

code:  當A[u] == cnt代表在第cnt筆測資時u為AP，用int型態省下初始化的時間，cnt記得++