[baekJoon11724] 연결 요소의 개수(DFS)

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

11724번: 연결 요소의 개수

---

IDEA: DFS

연결 요소의 개수를 count하기 위해 main함수에서 반복문을 돌렸다!

재귀 호출을 이용한 깊이 우선 탐색을 통해서 연결 되어있는 노드를 다 돌고 main함수로 돌아와서 cc값을 늘리는 방식이다.

---

/*
날짜: 2020.08.13
번호: 11724
문제: 방향 없는 그래프가 주어졌을 때,
      연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
*/
#include <iostream>
using namespace std;

int N; // 노드 개수
int graph[10001][10001] = { 0, };
int visit[10001] = { 0, };
int cc = 0; // 연결 요소의 개수

void dfs(int node) {
	visit[node] = 1; // 방문함

	for (int i = 1; i <= N; ++i) {
		
		/* 방문하지 않은 노드이면서 연결된 노드 탐색 */
		if (!visit[i] && graph[node][i] == 1) {
			dfs(i);
		}
	}
}

int main() {
	int M; // 간선 개수
	int u, v; // 연결된 노드 번호
	cin >> N >> M;

	while (M--) {
		cin >> u >> v;
		graph[u][v] = graph[v][u] = 1;
	}

	for (int i = 1; i <= N; ++i) {
		if (!visit[i]) {
			dfs(i);
			cc++; // 연결된 노드들을 다 돌고 오면!
		}
	}

	cout << cc << "\n";
}