[백준] 2606번 바이러스(python)

문제)

알고리즘)

- graph에 각 컴퓨터의 연결(인접 리스트 방식) 구서

- DFS 탐색을 하며 1번 컴퓨터와 연결된 컴퓨터 카운트

 

 

 

코드)

#바이러스
import sys
input = sys.stdin.readline

cnt = int(input())
graph = [[] for _ in range(cnt+1)]
visited = [] #방문한 컴퓨터 넘버

test = int(input())
for _ in range(test):
    index, link = map(int, input().split())
    graph[index].append(link)
    graph[link].append(index)

#dfs 
def dfs(start, graph, visited):
    for i in graph[start]:
        if i not in visited:
            visited.append(i)
            dfs(i, graph, visited)


dfs(1, graph, visited)
print(len(visited)-1) #1번컴퓨터를 제외하기 위해 -1