[BOJ] 11724 연결 요소의 개수

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

문제 요약

• 방향이 없는 그래프가 주어진다.

접근

• 두 정점이 A, B와 같이 주어지는 경우 A->B, B->A와 같이 양방향에서 접근이 가능하도록 한다.
• 방문 체크를 한 변수를 만들고 탐색하지 않은 경우 탐색한다.
• DFS를 통해 해당 정점과 인접한 다른 정점을 탐색한다.

코드

import sys
sys.setrecursionlimit(10**8)
n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)
def dfs(v):
    visited[v]=True
    for i in graph[v]: # 정점 v와 인접한 정점 i를 순차적으로 검사
        if not visited[i]:
            dfs(i)
for i in range(m):
    u,v=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)
cnt=0
for i in range(1,n+1):
    if not visited[i]: # 정점 i를 기준으로 방문하지 않은 경우
        dfs(i)
        cnt+=1
print(cnt)