[C++] 백준 11724번 문제풀이

처음 문제를 읽고 연결요소란 말을 잘 이해 못해서 헷갈렸다.

간단히 말하면 정점 하나를 DFS 탐색 했을 때 하나의 연결요소가 생긴다

정점 하나가 DFS 탐색 했을 때 지나갔던 정점들은 그 연결요소에 해당되며

지나가지 않았던 정점들을 다시 DFS 하면서 연결요소를 찾으면 된다

DFS 기본을 구현할 줄 알면 쉽게 풀 수 있는 문제였다.

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

vector<int> vc[1001];
bool visited[1001];
void DFS(int n) {
	visited[n] = true;
	for (int i = 0; i < vc[n].size(); i++) {
		int check = vc[n][i];
		if (!visited[check]) {
			DFS(check);
		}
	}

}
int main() {
	int N, M;
	cin >> N >> M;
	while (M--) {
		int x, y;
		cin >> x >> y;
		vc[x].push_back(y);
		vc[y].push_back(x);
	}
	int total = 0; //연결요소 개수
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			DFS(i);
			total++;
		}
	}
	cout << total << endl;	

}