[백준/파이썬] 11724번 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

간단한 dfs문제이다. bfs로도 풀 수 있지만 dfs 연습중이라 그냥 dfs로 풀었다

 

무방향이므로 양쪽으로 모두 다 입력받아주고, 방문하지 않은 노드에 대해서만 dfs 탐색을 진행해준다.

dfs 탐색이 끝난다면, 하나의 '연결요소'에 대한 탐색이 끝난 것과 동일한 것이므로 정답 개수를 +1 해주면 된다!

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():  
  global ans
  for i in range(1,n+1):
    if not visited[i]:
      visited[i] = True
      dfs(i)
      ans +=1
  print(ans)
  
def dfs(node):
  for i in tree[node]:
    if not visited[i]:
      visited[i] = True
      dfs(i)
    
if __name__ == "__main__":
  n,m = map(int,input().split())
  tree = [ [] for _ in range(n+1)]
  visited = [False for _ in range(n+1)]
  ans=0
  
  for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
  
  main()