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

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

---

기본적인 DFS 알고리즘에 "연결 요소의 개수"를 세는 기능을 추가한다.

DFS가 한 번 호출될 때 마다 연결 요소는 하나씩 늘어나게 만들면 된다.

 

import sys
sys.setrecursionlimit(5000)

N,M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False for i in range(N+1)]
visited[0] = True

def dfs(v):
    visited[v]=True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

count = 0
for i in range(len(visited)):
    if not visited[i]:
        dfs(i)
        count += 1

print(count)

 

---

배운점

- DFS 입력 방식을 바꾸기

# 간선과 간선 사이의 관계
[
[1 2]
[2 5]
[5 1]
[3 4]
[4 6]
]

--------------
# n번 노드가 어떤 노드와 연결되어 있는지의 관계
[[],[2],[5],[4],[6],[5],[]]

graph = [[] for _ in range(N+1)]
for _ in range(M):
	a ,b = mpa(int, sys.stdin.readline().split())
    graph[a].append(b) #n번 인덱스에, 어떤 노드와 연결되어 있는지 넣는다.
    graph[b].append(a) #반대의 경우도 넣는다.

- 가장 간단한 dfs 함수

def dfs(v):
    visited[v]=True
    for i in graph[v]: #그래프 확인
    	if not visited[i]: #방문 여부 확인
            dfs(i)

- 재귀 함수 최대 횟수 설정

import sys
sys.setrecursionlimit(5000)