125 - Numbering Paths

Background

由輸入資料產生出肯定或否定(yes or no)兩種答案的問題被稱為「判定性問題」(decision problems)。一個典型的判定性問題是NP-完備性問題(NP-complete problems)，這種問題並無法用一般通用而有效率的方法處理。有些問題與判定性問題一樣單純，不過要試著列舉出所有肯定的答案就很困難了(或至少會花很多時間)。

這問題關於車輛在一個僅含單向道路的城市中，如何決定所有可能路徑的總數。

The Problem

給定城市中所有由道路連接的交叉點，你必須寫一個程式決定每個交叉點之間所有可能路徑的總數，一條路徑是由一節點到另一節點之間所依序經過的道路集合。

城市內的點由0開始被賦予編號，一條單向道路會由兩個節點來指定，例如表示由節點 j 到節點 k 的單向道路，注意，雙向道路可藉由定義兩條對向的道路來處理： 與 。

考慮一個有四個節點，並以以下四條單向道路所連結的城市：

0  1
0  2
1  2
2  3

由 0 到 1 之間共有 1 條可能的路徑，由 0 到 2 之間共有 2 條可能的路徑( 及 )，由 0 到 3 有 2 條路徑，1 到 2 有 1 條，1到 3 有 1 條，2 到 3 有 1 條。
兩點之間的路徑可能存在有無限多條，例如上例中再增加一條由 3 到 2 的路徑，則由 0 到 2 的路徑選擇會變的有無限多條，因為可藉由 2 3 之間來來回回來增加路徑總數，因此路徑 與路徑 是不同的。

The Input

輸入會有許多城市的道路資訊，一開始會有該城市的單行道總數，接著是每條由 j 到 k 的單行路，以 j k 來表示。所有測試資料的節點編號都是由 0 開始依序增加。所有輸入中的整數都以空白字元分隔，並以EOF結束。

不會存在有連接相同節點的道路。

The Output

針對每個城市請輸出所有節點兩兩之間所存在的路徑總數，其輸出的格式請用矩陣的形式表示，假設該矩陣定義為M，則 M[j][k]表示每個由 j 到 k 的不同路徑總數，輸出矩陣時請以矩陣的「列順序」(row-major order)來表示，矩陣的每列輸出為一列。在輸出矩陣之前請先輸出"matrix for city k'"，k以 0 開始表示城市的編號，。

若兩節點之間存在有無窮多組路徑選擇，請輸出 -1，每列之間的整數請以空白字元隔開。

Sample Input

7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
5 
0 2 
0 1 1 5 2 5 2 1
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1

Sample Output

matrix for city 0
0 4 1 3 2
0 0 0 0 0
0 2 0 2 1
0 1 0 0 0
0 1 0 1 0
matrix for city 1
0 2 1 0 0 3
0 0 0 0 0 1
0 1 0 0 0 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
matrix for city 2
-1 -1 -1 -1 -1
0 0 0 0 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0 0 0 0

原文出處