알고리즘 - Python / 백준 - 11724번 : 연결 요소의 개수

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

 

---

풀이

• 연결 요소의 개수를 구하는 문제이기에 BFS나 DFS로 풀면 된다고 생각하고 접근
• DFS 해결하였고 , 연결된 노드들의 묶음을 찾는다고 생각해 그래프 - VISTIED 노드 를 반복해서 체크해 모든 노드를 돌았을 때 종료하도록 하였음
• 이렇게 구현한 후 예제를 확인하고 제출 하였는데 틀렸다고 나옴 , 반례를 찾아보니 연결이 되어있지 않는 노드들도 간선이 0인 상태로 연결되었다고 보아야 한다는 점을 찾음 ( 즉 , 노드 1 2 3 4 5 6 중에 1-2 1-3 이라면 나머지 4 , 5 , 6 도 4-4 , 5-5 , 6-6 이런 식으로 간선을 거치지 않아도 된다는 것이다.
• 따라서 남아있는 노드의 개수를 이전에 구한 최종 답에 더해 정답

 

import sys

n , m = map(int , sys.stdin.readline().split())

dic = {}

def dfs(dic, root):
  visited = []
  stack = [root]

  while stack:
    n = stack.pop()
    if n not in visited:
      visited.append(n)
      if n in dic:
        sub_stack = list(set(dic[n]) - set(visited))
        stack += sub_stack
  return visited

stack = []

for _ in range(m):
  nd1, nd2 = map(int , sys.stdin.readline().split())
  stack.append(nd1)
  stack.append(nd2)

  if nd1 not in dic:
    dic[nd1] = [nd2]
  else:
    dic[nd1].append(nd2)
  
  if nd2 not in dic:
    dic[nd2] = [nd1]
  else:
    dic[nd2].append(nd1)

ans = 0
stack = list(set(stack))
stack_len = len(stack)
while stack:
  vs = dfs(dic ,stack[0])
  if len(vs) != 0:
    ans += 1
  stack = [x for x in stack if x not in vs]

print(ans + n - stack_len)

---