[c++/백준] 11724 연결 요소의 개수

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

11724번: 연결 요소의 개수

연결 요소가 뭔지 몰라서 문제에서 나온 예제를 직접 그려보며 이해했다. 

연결 요소의 개수는 간단하게 말해서 각각 서로 연결되지 않은 그래프의 개수이다. 

 

dfs를 이용하여 탐색을 하였고, main문에서 일정한 조건으로 반복문을 돌리면서 cnt를 ++해주었다. 

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

int n, m;
int map[1001][1001];
bool isVisited[1001] = { false };
int ans = 0;

void dfs(int k) {
	isVisited[k] = true;

	for (int i = 1; i <= n; i++) {
		if (isVisited[i] == false && map[k][i] == 1) {
			isVisited[i] = true;
			dfs(i);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}

	//for문 돌리면서 isVisited가 false이면 cnt++해줌
	for (int i = 1; i <= n; i++) {
		if (isVisited[i] == false) {
			ans++;
			dfs(i);
		}
	}
	cout << ans;
}

난이도는 그닥 높지 않은듯