ネットワーク

4825 ワード
DFS/BFS テキストリンク

プログラマ


ネットの数量を求めます
  • コンピュータ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
    プログラマコード問題2021、02/15-Lv.さっきの歌
    iOS 7から追加されたMKDirectionsで経路検索を試してみる