[BOJ / Python] 11724번: 연결 요소의 개수

문제: BOJ 11724번

풀이

그래프가 주어지고 연결 요소의 개수를 구해야 하니 서로 연결되지 않은 그래프 노드 묶음들의 개수를 찾으면 된다.
DFS알고리즘에 1번노드부터 순서대로 넣는다. N개의 노드를 다 DFS에 넣으면서, 방문하지 않았다면 1씩 올라가는 카운트를 만들면 그 카운트가 답이 될 것이다.

최종코드

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

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

def dfs(v):		#dfs
    vis[v]=1
    for i in range(n+1):
        if graph[v][i]==1 and vis[i]==0:
            dfs(i)

for i in range(m):
    x,y=map(int,input().split())
    graph[x][y]=1
    graph[y][x]=1		#인접행렬방식

for i in range(1,n+1):
    if vis[i]==0:
        dfs(i)				#1번노드부터 끝노드까지 돌린다. 
        ans+=1				#방문 안되있으면 +1을 한다.

print(ans)