ネットワーク

方法

いろいろな方法を試した.いつも2つのテストケースしか合格していないので、質問欄である感謝の人が反例をアップロードしているのを見て分かった.
最初は、dfsを使用して特定のグラフィックの1を追跡し、解凍します.これにより、次の場合に失敗することになります.
[[1, 1, 0, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 1]]

だから別のグラフを作って、dfsで巡回する方法でそれに近づくことにしました.
次のようにします.

コード#コード#

def dfs(x, graph, visited):
    if visited[x] == True:
        return
    visited[x] = True
    for val in graph[x]:
        dfs(val, graph, visited)

def make_graph(n, matrix):
    graph = dict()
    for i in range(n):
        graph[i] = []
        for j in range(n):
            if i != j and matrix[i][j] == 1:
                graph[i].append(j)
    return graph

def solution(n, computers):
    graph = make_graph(n, computers)
    cnt = 0
    visited = [False] * n
    for x in graph:
        if visited[x] == False:
            dfs(x, graph, visited)
            cnt += 1
    return cnt