中等 時間限制:3 s記憶體限制:128 MB

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
開啟討論
開啟紀錄

登入後即可撰寫程式、測試範例及提交解答。

登入