알고리즘 :: 백준 :: DFS :: 11724 :: 연결 요소의 개수

문제

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

문제접근

• 그래프의 연결요소 문제는 꼭 알아둬야하는 기본 DFS, BFS 패턴 문제다.
• 그래프의 연결요소 개수는 임의의 시작점에서 DFS를 수행한 뒤 반환 될 때마다 하나씩 카운트한 것과 같다.
• 이것이 가능한 이유는 DFS 또는 BFS를 수행하면 하나의 부분 그래프를 모두 탐색하게 되기 때문이다.
  다음 번 시작점에서 다른 부분 그래프를 탐색하게 된다.

코드

#include <iostream>
#include <vector>
using namespace std;

static int N, M;
static vector<int> graph[1001];
static vector<bool> isVisited(1001);

void dfs(int here) {
	isVisited[here] = true;
	for (const int& there : graph[here])
		if (!isVisited[there]) dfs(there);
}

int solve() {
	int ret = 0;
	for (int start = 1; start <= N; ++start) {
		if (!isVisited[start]) {
			dfs(start);	
			ret++;	// DFS 종료하고 리턴될 때 마다 카운팅
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int start = 0, end = 0;
		cin >> start >> end;
		graph[start].push_back(end);
		graph[end].push_back(start);
	}
	cout << solve() << '\n';
}

결과