[ dominator tree ] 有向圖的支配樹

dominator tree，中文名稱叫支配樹
給一張有向圖$G$，我們從其中一個點$r$出發到$y$的所有路徑中，一定會經過點$x$，就稱$x$是$y$的必經點；我們把距離$y$最近的必經點稱為最近必經點，記為$idom(y)$。
支配樹上的有向邊$(u,v)$滿足$idom(v)=u$，那對於一個點$y$，$y$的所有必經點就會是支配樹上$r$到$y$路徑上的所有點。
這個東西可以求有向圖的割點、橋(在每個邊加入虛擬點)等等。
注意code裡的$idom$跟我定義的不一樣
我是看這份講義的偽代碼寫出來的：