백준 / 연결 요소의 개수 / 11724

Question

문제링크
Silver 2

Logic

기본 구조 : dfs
1. 입력 정보를 바탕으로 그래프를 2차원 배열 li로 구현한다.
2. 탐색 여부를 판단하는 visit 리스트를 둔다.
3. 아직 탐색하지 않은 정점에 대해, dfs를 실행한다.
4. dfs가 실행되면, 그와 연결되어 있는 모든 정점을 방문한다.
5. 마지막 정점까지 탐색하면, dfs가 호출된 횟수를 출력한다.

Code

import sys
sys.setrecursionlimit(10000)

N,M= map(int,sys.stdin.readline().split())
visit = [0 for i in range(N+1)]
li = [[0 for __ in range(N+1)] for _ in range(N+1)]

for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    li[a][b]=1
    li[b][a]=1

def dfs(v):
    visit[v]=1
    for i in range(1,N+1):
        if visit[i]==0 and li[v][i]==1:
            dfs(i)

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