[백준]11724번: 연결 요소의 개수

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

11724번: 연결 요소의 개수

---

둘 다 해보니 bfs가 좀 더 빨랐다

 

1. 백준에서는 dfs하면 자꾸 RecursionError가 난다

 -최대 재귀 깊이 설정값을 바꿔주면 되긴 하는데 이게 매번 해주기 좀 귀찮다

 

2. 그래프 요소 입력받을 때 input()으로 받으니 시간초과가 났다.

 -sys.stdin.readline()으로 받으면 해결됨

from collections import deque
import sys
sys.setrecursionlimit(10**6)

def dfs(x):
  if visited[x]==1:
    return False
  
  visited[x]=1 #방문 처리
  #연결된 방문 가능한 요소들을 시작점으로 dfs 후 true를 리턴
  for i in graph[x]: 
    if visited[i]==0:
      dfs(i)
  return True
  
def bfs(x):
  if visited[x]==1:
    return False
    
  visited[x]=1 #방문 처리
  q = deque()
  q.append(x)

  while q:
    cur = q.popleft()
    for i in range(len(graph[cur])):
      next = graph[cur][i]
      if visited[next]==0:
        visited[next]=1 #방문처리
        q.append(next)
  return True

#그래프 정보 입력받기
n,m = map(int,sys.stdin.readline().split())
graph=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,sys.stdin.readline().split())
  graph[a].append(b)
  graph[b].append(a)


visited = [0]*(n+1)

#연결요소 개수 카운트하기
cnt=0
for i in range(1,n+1):
  if dfs(i)==True:
    cnt += 1
print(cnt)