[백준] 11724번 연결 요소의 개수(python)

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

11724번: 연결 요소의 개수

 

1. 난이도 실버2 (🥈)

 

2. 내가 작성한 코드

import sys

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

n, m = map(int, input().rstrip().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
  a,b = map(int, input().rstrip().split())
  graph[a].append(b)
  graph[b].append(a)
  
visit = [0]*(n+1)
visit[0] = 1

def dfs(i):

  visit[i] = cnt

  for j in graph[i]:
    if visit[j] == 0:
      visit[j] = cnt
      dfs(j)
      

cnt = 0

for i in range(1,n+1):
  if visit[i] == 0:
    cnt+=1
    dfs(i)

print(max(visit))

 

dfs에서 sys.setrecursionlimit(10**6) 을 작성해주는 것을 놓치면 런타임 에러가 발생하니 잊지 말기!

 

연결요소란 나누어진 각각의 그래프를 의미한다.

 

(참고 : https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component)

 

 

 

나는 dfs를 이용해서 본 문제를 해결했다.

 

1. 인접리스트를 만들고, 연결되어있는 정점의 list에 삽입해준다.

 

2. visit를 n개 만들어야 하지만 그래프의 정점이 1부터 시작하기 때문에 편의상 0부터 n개까지 n+1개 만들어준다.

 

3. 0은 방문처리 해준다.

 

4. visit를 방문하지 않은 위치를 찾으면 dfs를 실행시킨다.

(이 때, dfs를 실행시킬 때마다 cnt를 1씩 추가하여 연결개수가 증가되었음을 카운팅한다.)

 

5. visit의 max값은 연결개수의 개수 이기때문에  max(visit)를 return해준다.