最新華為OD機試

真題目錄：點擊查看目錄
華為OD面試真題精選：點擊立即查看

題目描述

快遞業務范圍有 N 個站點，A 站點與 B 站點可以中轉快遞，則認為 A-B 站可達，
如果 A-B 可達，B-C 可達，則 A-C 可達。
現在給 N 個站點編號 0、1、…n-1，用 s[i][j]表示 i-j 是否可達，
s[i][j] = 1表示 i-j可達，s[i][j] = 0表示 i-j 不可達。
現用二維數組給定N個站點的可達關系，請計算至少選擇從幾個主站點出發，才能可達所有站點（覆蓋所有站點業務）。
說明：s[i][j]與s[j][i]取值相同。

輸入描述

第一行輸入為 N，N表示站點個數。 1 < N < 10000
之后 N 行表示站點之間的可達關系，第i行第j個數值表示編號為i和j之間是否可達。

輸出描述

輸出站點個數，表示至少需要多少個主站點。

用例

輸入	4 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1
輸出	1
說明	選擇 0 號站點作為主站點， 0 站點可達其他所有站點， 所以至少選擇 1 個站點作為主站才能覆蓋所有站點業務。

輸入	4 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1
輸出	3
說明	選擇 0 號站點可以覆蓋 0、1 站點， 選擇 2 號站點可以覆蓋 2 號站點， 選擇 3 號站點可以覆蓋