CPE OJ - B002 - City Network
CPE OJ - B002 - City Network
來源代碼:cpeoj
前往提交 ↓
某個國家正在整理城市之間的交通網路。
全國共有 n 座城市,編號為 1 到 n。如果兩座城市之間存在直接道路,則它們可以互相往來。此外,即使兩座城市之間沒有直接道路,只要能透過其他城市一路抵達,它們仍然屬於同一個交通區域。
例如:
城市 1 與城市 2 有道路相連
城市 2 與城市 3 有道路相連
即使城市 1 與城市 3 之間沒有直接道路,城市 1 仍然可以經由城市 2 到達城市 3,因此這三座城市屬於同一個交通區域。
現在給定所有城市之間的連接狀況,請計算全國一共可以分成多少個彼此獨立的交通區域。
限制:
1 ≤ n ≤ 200
輸入矩陣中的每個值皆為 0 或 1。
對所有 i:
a_{i,i}=1
且對所有 (i,j):
a_{i,j}=a_{j,i}
輸入說明
第一行包含一個整數 n,表示城市數量。
接下來有 n 行,每行包含 n 個整數。
第 i 行的第 j 個數字表示城市 i 與城市 j 的連接狀況:
1:兩座城市之間有直接連接。0:兩座城市之間沒有直接連接。
所有道路皆為雙向,因此若城市 i 可以直接到達城市 j,城市 j 也可以直接到達城市 i。
每座城市都視為與自己相連。
輸出說明
輸出一個整數,表示彼此獨立的交通區域數量。
輸入輸出範例
範例 1
範例輸入
3 1 1 0 1 1 0 0 0 1
範例輸出
2
範例 2
範例輸入
4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
範例輸出
4
範例 3
範例輸入
6 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1
範例輸出
2
登入後即可撰寫程式、測試範例及提交解答。
登入