# 2606 바이러스

n = int(input()) # 컴퓨터의 수 
m = int(input()) # 연결된 컴퓨터 쌍의 수 

graph = [ [] for _ in range(n+1) ]      # 컴퓨터 연결 관계를 나타낸 그래프 

for i in range(m):
  a, b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [ False ] * ( n+1 )

def dfs(graph, v, visited): 
  visited[v] = True 
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

dfs(graph,1,visited)

cnt = -1
for i in range(n+1):
  if visited[i] == True :
    cnt += 1 

print(cnt)

 

방법 :  BFS 를 이용해서 풀이. 

유의 :  graph 를 채우는 과정에서, graph[b].append(a) 를 안했더니 틀렸다는 결과를 받았음.

 

 

www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

=> 좀 더 간결한 풀이

n = int(input()) # 컴퓨터의 수 
k = int(input()) # 쌍의 수 

graph=[ [] for _ in range(n+1) ]
for i in range(k):
  s, e = map(int,input().split())
  graph[s].append(e)
  graph[e].append(s)

visited = [False]*(n+1)

def dfs( graph, v, visited):

  if visited[v] :
    return False 
  
  visited[v]= True 
  
  for i in graph[v]:
    dfs( graph,i,visited)
  return True 

dfs(graph,1,visited)

print(visited.count(True)-1)