[アルゴリズム]ネットワーク

项目网络的问题

もんだいぶんせき

問題そのものは難しくない.これは,計算機数nと計算機との接続関係を表す2次元配列(0は非接続,1は接続)を受信することによって,どれだけの完全なネットワークが形成されるかを求める.このとき,ネットワーク単位は接続単位である.すなわち、一例に示すように、1、2は接続されており、3は単独で隔てられており、この場合、2つのネットワークが存在する.

インプリメンテーションコード

def solution(n, computers): graph = {} path = {} answer = 0 for i in range(n): graph[i] = [] for idx, el in enumerate(computers[i]): if el == 1 and i!=idx: graph[i].append(idx) def dfs(node): for el in graph[node]: try: if path[el]: continue except: path[el] = True dfs(el) for key in list(graph.keys()): try: if path[key]: continue except: answer += 1 dfs(key) return answer