ネットワーク

プログラマ

ネットの数量を求めます

コンピュータAはコンピュータBに直接接続されており、コンピュータBがコンピュータCに直接接続されている場合、コンピュータAとコンピュータCは間接的に接続されて情報を交換することもできる.そのため、コンピュータA、B、Cは同じネットワーク上に存在する.

計算機の個数nは、接続情報を含む2次元配列計算機をパラメトリック化した場合、ネットワークの個数を返すために解関数を記述してください.

コンピュータの数nは、1つまたは複数の200以下の自然数である.

各コンピュータは、0からn−1までの整数として表される.

コンピュータ番号が

iの場合、コンピュータ[i][j]は1として表される.

コンピュータ[i][i]は常に1である.

にゅうしゅつりょく

ncomputersreturn3[[1, 1, 0], [1, 1, 0], [0, 0, 1]]23[[1, 1, 0], [1, 1, 1], [0, 1, 1]]1

方法

インデックスでアクセスします.iの1番目の要素のネットワークを表示するには、iの1番目の配列を表示します.
アクセスするテーブルを配置し、i配列の要素を迂回し、アクセス値が1のインデックスjにする.
隣接する場合、while文の終了時にアクセスするテーブルはすべて1です.そうしないと、非隣接インデックスは0になります.
アクセス値が0のインデックスに対して関数を実行します.関数が終了すると、カウントが報告されます.

コード#コード#

from collections import deque

def bfs(n, i, computers, visited):
    q = deque()
    visited[i] = 1
    q.append(i)
    
    while q:
        v = q.popleft()
        for j in range(len(computers[v])):
            if computers[v][j] == 1 and visited[j] == 0:
                visited[j] = 1
                q.append(j)
    
def solution(n, computers):
    visited = [0]*n
    cnt = 0
    for i in range(len(computers)):
        if visited[i] == 0:
            bfs(n, i, computers, visited)
            cnt += 1
    return cnt