11902 - Dominator

在圖論中，我們說節點X「支配(dominate)」節點Y，表示由某特定節點(起點)出發，到達節點Y的所有路徑必定會經過節點X，若由起點出發並不存在任何路徑到達節點Y，則節點Y並不被任何節點所支配。並且我們定義可從起點到達的所有節點被自身所支配。本題給定一有向圖，請你找出所有節點的支配節點， 並且我們定義第零節點為起點。

例如右圖中的節點3即為節點4的支配節點，因為從節點0到節點4的所有路徑必通過節點3，而節點1並非節點3的支配節點，因為路徑 0 2 3 並不通過節點1。

Input

輸入資料的第一列為整數T(<= 100)表示測試資料的組數。

每組資料的第一個整數N(0 < N < 100)表示圖中節點的總數，接下來的N列，每列有N個整數，若第 i 列中的第 j 個(由0開始)整數為1，表示由節點 i 到節點 j 有一有向的邊，若為0則否。

Output

請每組測試資料輸出其資料編號，並在接下來的2N+1列中輸出任兩節點的支配關係，若節點A支配節點B請在(A, B)的位置上輸出"Y"，否則請輸出"N"，(A, B)的位置表示第A列的第B欄，其格式請參考範例資料。

Sample Input	Output for Sample Input
2 5 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1	Case 1: +---------+ |Y|Y|Y|Y|Y| +---------+ |N|Y|N|N|N| +---------+ |N|N|Y|N|N| +---------+ |N|N|N|Y|Y| +---------+ |N|N|N|N|Y| +---------+ Case 2: +-+ |Y| +-+

---

原文出處