[白俊]2606号:ウイルス(Python)

4902 ワード
解答白俊 DFS テキストリンク

質問する



私の答え

n=int(input())
m=int(input())
g=[[] for i in range(n+1)]#n+1개의 노드를 갖는 그래프 생성

for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)#a노드에 b연결
    g[b].append(a)#b노드에 a연결

visited=[0]*(n+1) #방문한 노드 저장, 방문했으면 1로 변경

def dfs(n):
    visited[n]=1
    for i in g[n]:
        if visited[i]==0:#방문하지 않았다면
            dfs(i)#방문처리
    return sum(visited)#방문한 노드 수(1의 개수)

print(dfs(1)-1)#1번을 제외한 컴퓨터 수
方法
  • 1番のコンピュータからアクセスを開始し、n+1ノードのグラフを生成します.
  • 以降、各ペアを接続する幹線は、繰り返し文によって生成される.
  • がアクセスするノードは0ではなく1として格納される.
  • dfs関数では、アクセスノードであるかどうかを判断し、アクセスノードの数を返します.
  • 感染したパソコンの数は1を含まないので、-1にあげます.
    • 191. Terminal
    JUnit 4学習(二)異常と無視テスト