[백준 - 11724] 연결 요소의 개수 [C++]

1. 문제

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

11724번: 연결 요소의 개수

 

2. 설명

: 무방향 그래프가 주어졌을 때, 방문하지 않은 정점에 대해 dfs로 그 정점과 연결된 모든 정점들을 방문하며 visited배열에 체크해줍니다. 그렇게 한다면 아래 코드에서 cnt++가 실행되는 횟수가 결국 연결 요소(Connected Component)의 개수가 됩니다.

 

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;
vector <int> v[1001];
int n, m, x, y, cnt;
bool visited[1001];

void dfs(int x) {
	visited[x] = true;
	for (int i = 0; i < v[x].size(); i++) {
		int n = v[x][i];
		if (!visited[n]) dfs(n);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			cnt++;
			dfs(i);
		}
	}
	cout << cnt;
	return 0;
}