백준 11724 c++ "연결 요소의 개수" -PlusUltraCode-

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

 

 

[필자 사고]

이 문제는 그래프 탐색의 기초 문제라고 생각한다.

 

문제에서 요구하는 내용은 연결요소의 개수를 요구한다.

 

연결요소란 노드들간의 연결관꼐를 말한다. 즉 집합의 갯수를 말하는 것과 같다.

 

A집단과 B집단이 있다고 한다면 연결요소는 2경우라고 생각하면 된다.

 

필자는 DFS탐색을 통해 같은 집단에 있는 아이들을 방문처리하였고 

다른 방문되지 않는 곳을 탐색할 때마다 resultCount 의 숫자를 증가 시켜 

연결요소의 갯수를 구했다.

 

[소스 코드]

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int resultCount = 0;
vector<vector<int>> arr;
vector<bool> visited;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	visited.resize(N + 1, false);
	
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		arr[start].push_back(end);
		arr[end].push_back(start);
	}
}

void DFS(int startIdx) {

	if (visited[startIdx])return;
	visited[startIdx] = true;
	for (int nextIdx : arr[startIdx]) {
		if (visited[nextIdx] == false)DFS(nextIdx);
	}
}

void GameStart() {
	for (int i = 1; i <= N; i++) {
		if (visited[i] == true)continue;
		resultCount++;
		DFS(i);
	}
}

int main(void) {
	Input();
	GameStart();
	cout << resultCount;
}