[Baekjoon] 11724번 : 연결 요소의 개수

1. 문제

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

• 그래프, DFS, BFS 문제

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

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

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

// 예제 입력 1 
6 5
1 2
2 5
5 1
3 4
4 6

// 예제 출력 1 
2

// 예제 입력 2 
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

// 예제 출력 2 
1

2. 핵심 아이디어

• 노드들을 간선을 따라 DFS, BFS로 돌면서 방문한 노드들은 방문기록을 남김

3. Python 문제풀이

import sys
sys.setrecursionlimit(5000)
input = sys.stdin.readline

def dfs(start, depth) :
  visited[start] = True
  for i in graph[start] :
    if not visited[i] :
      dfs(i, depth+1)

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m) :
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [False] * (n + 1)
cnt = 0

for i in range(1, n+1) :
  if not visited[i] :
    if not graph[i] :
      cnt += 1
      visited[i] = True
    else :
      dfs(i, 0)
      cnt += 1

print(cnt)

4. Java 문제풀이