연결 요소의 개수

---

문제

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

---

풀이

1. BFS와 DFS의 탐색방법을 통해 그래프를 탐색한다
2. 탐색되지않은 정점이 있다면 그 정점을 시작으로 다시 탐색하고, 횟수 카운트
3. 모든 정점이 탐색됫다면 종료

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 1000+1
int N,M;
vector<int> graph[MAX];
bool visited[MAX];
queue<int> q;
int totalCount = 1;



void bfs(int v) {
	visited[v] = true;

	q.push(v);

	while (!q.empty())
	{
		int parent = q.front();
		q.pop();

		for (int i = 0; i < graph[parent].size(); i++)
		{
			int child = graph[parent][i];
			if (!visited[child])
			{
				visited[child] = true;
				q.push(child);
			}
		}
	}
}

int checkEnd() {
	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
		{
			return i;
		}
	}

	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N>>M;
	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		grape[x].push_back(y);
		grape[y].push_back(x);
	}

	bfs(1);
	int che = checkEnd();

	while (che !=0)
	{
		bfs(che);
		che = checkEnd();
		totalCount++;
	}

	cout << totalCount;
}