[코딩테스트]bj11724 연결 요소의 개수 - C++

[문제]

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

[입력]

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.(1<=N<=10000, 1<M<M*(N-1)/2)
둘째 줄부터 M개의 줄에 간선의 양 끝점 U와 V가 주어진다. (1<=U,V<=N,u!=v) 같은 간선은 한번만 주어진다.

[출력]

첫째 줄에 연결 요소의 개수를 출력한다.

[접근]

무방향 그래프 문제이다.
그래프를 구현하는 방법은 크게 이차원 배열과, 연결 리스트로 나뉜다.

그래프에서 연결 요소(connected components) 라는 것은 다음 조건을 만족 시켜야한다.
1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야한다.
2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

이와 같은 연결 요소를 구하기 위해서 bfs, dfs를 이용해야 한다

[코드]

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std; 

vector<int> graph [1001];
bool visited[1001];

void dfs(int v) {
	visited[v] = true; 
	for (int i = 0; i < graph[v].size(); i++) {
		int next = graph[v][i];
		if (visited[next] == false)
			dfs(next);
	}
}

int main() {
	int N, M; //정점, 간선
	int count=0;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v; 
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i < N; i++) {
		if (visited[i] == false) {
			dfs(i);
			count++;
		}
	}
	cout << count;
	return 0; 
}