백준 11724번: 연결 요소의 개수

문제 링크: https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

아이디어 : DFS

이것은 정점 기준으로 방문체크해주면서, Main 문에서 실행 한 DFS 카운트 횟수를 계산하는 것이 포인트.

 

의견 : BFS를 풀고 싶어서 찾은건데, DFS로 푸는 것이 맞다 생각했다.

그리고 DFS 기본 구현을 하면 풀 것 같다.

 

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

int N, M;
int nCount;

vector<int> v[1001];
bool bChecked[1001];

void DFS(int x)
{
	if (bChecked[x]) return;
	bChecked[x] = true;
		

	for (int i = 0; i < v[x].size(); i++)
	{
		int temp = v[x][i];

		DFS(temp);
	}
}

int main(void)
{
	cin >> N >> M;
	int nNum1, nNum2;

	for (int i = 0; i < M; i++)
	{
		cin >> nNum1 >> nNum2;
		v[nNum1].push_back(nNum2);
		v[nNum2].push_back(nNum1);
	}

	for (int i = 1; i <= N; i++)
	{
		if(!bChecked[i])
		{ 
			DFS(i);
			nCount++;
		}
	}

	cout << nCount << endl;
	return 0;
}