[C++, 백준/11724번] 연결 요소의 개수

 

---

☑️ [C++, 11724번] 연결 요소의 개수

1️⃣ 문제

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

2️⃣ 접근

크래프톤 정글에서 제공한 문제를 다시 풀고 있다. 블로그에도 Python으로 풀이한 내용을 올린 적이 있는데, 접근 방법이 다르지 않다.

 

[Python, 백준/11724번] 연결 요소의 개수

 

그동안 프로그래밍에 소홀해서 그런가 의사 코드를 작성하는 것보다 C++로 풀이하는 것이 어려웠다... 다시 열심히 해보자!

 

3️⃣ 코드

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

typedef vector<vector<int>> Graph;

Graph createGraph(int vertex_count, int edge_count) {
	Graph graph(vertex_count + 1);

	for (int i = 0; i < edge_count; ++i) {
		int from, to;
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	return graph;
}

void visitDFS(const Graph& graph, int currentVertex, vector<bool>& visited) {
	visited[currentVertex] = true;

	for (int vertex_num : graph[currentVertex]) {
		if (!visited[vertex_num])
		{
			visitDFS(graph, vertex_num, visited);
		}
	}
}

int countConnectedVertex(const Graph& graph, int vertex_count) {
	vector<bool> isVisited(vertex_count + 1, false);
	int connectedVertexCount = 0;

	for (int vertex = 1; vertex <= vertex_count; ++vertex) {
		if (!isVisited[vertex]) {
			++connectedVertexCount;
			visitDFS(graph, vertex, isVisited);
		}
	}

	return connectedVertexCount;
}

int main() {
	int vertex_count, edge_count;
	cin >> vertex_count >> edge_count;

	Graph graph = createGraph(vertex_count, edge_count);
	int result = countConnectedVertex(graph, vertex_count);

	cout << result << endl;

	return 0;
}