<문제>
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
<문제 풀이>
#BFS
from collections import deque
def bfs(graph,v,visited):
queue = deque([v])
visited[v] = True
while queue:
v = queue.popleft()
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
n = int(input())
m = int(input())
graph = [ [] for i in range(n+1) ]
for _ in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
graph[a].sort()
graph[b].sort()
visited = [False]*(n+1)
bfs(graph,1,visited)
cnt = visited.count(True) - 1
print(cnt)
#DFS
def dfs(graph,v,visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
visited[i] = True
dfs(graph,i,visited)
n = int(input())
m = int(input())
graph = [ [] for i in range(n+1) ]
for _ in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
graph[a].sort()
graph[b].sort()
visited = [False]*(n+1)
dfs(graph,1,visited)
cnt = visited.count(True) - 1
print(cnt)
1번과 인접한 노드들과도 연결되지 않은 노드들인 4, 7번은 False상태일것 이므로 cnt에 포함이 되지 않습니다.