2010/03/04 路徑問題 (path)

問 題敘述

在一個古老的舊城市裡，所有的道路皆是單行道。但 因其道路缺乏規劃，故某些單行道所連接之路口可能完全相同且方向一樣。甚至於有單行道其起始路口與終點路口是同一個路口。為了發展該城市之觀光事業，該市 交通局決定重新規劃所有道路。但首要任務則必須先了解各路口之間可以通行之路徑數。請寫一個程式計算任意兩個路口之間有多少種不同的路徑。一個路徑是由一 個(含)以上不重複之單行道所組成(單行道、起始路 口、終點路口皆不可重複，但其餘路口可以重複)。
條件限制

1. 路口數
n最少為1最多為50，且路口編號由1至n。
2. 單行道數量
m最少為1最多為2500。

輸入檔格式 (c:\path\input.txt)

第一行有兩個整數n 和 m，以一個空白分開。接下來的m行 各有兩個整數，分別代表各單行道之起始及終點路口。

輸出檔格式 (c:\path\output.txt)

請以一個 n x n (n行 n列)的矩陣，列出 從路口i至路口j之路徑數，1<= i, j <= n。每一列i均應有n個整數，分別代表路口i至所有其它路口之路徑數。在同一列的數字請以一空白隔開。

輸入範例
5 6
1 1
1 2
2 3
4 3
5 4
5 4
輸出範例
1 2 2 0 0
0 0 1 0 0
0 0 0 0 0
0 0 1 0 0
0 0 2 2 0