[백준] 11724번 - 연결 요소의 개수

문제

입력

출력

풀이

연결 요소는 연결된 정점들의 집합을 뜻한다. 연결 요소를 판별하려면 한 정점에서 다른 정점까지 연결된 경로가 없는지로 판별할 수 있다. 방문 체크용 배열을 만들어 탐색한 정점은 방문 체크하고, 방문하지 못한 정점이 있다면 다시 탐색하여 탐색 횟수로 연결 요소 수를 구하였다. 간선의 개수가 커질 것을 고려해 인접행렬과 DFS로 구현하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
	vector<vector<int>> adj;
	int vNum;

public:
	Graph(int vertex) {
		vNum = vertex;
		adj.resize(vNum, vector<int>(vNum, 0));
	}
	void addEdge(int i, int j) {
		if (i >= 0 && i <= vNum && j >= 0 && j <= vNum) {
			adj[i][j] = 1;
			adj[j][i] = 1;
		}
	}
	void DFS(const int& now, vector<bool>& visited) const{
		visited[now] = true;
		for (int i = 0; i < vNum; ++i) {
			if (adj[now][i] && !visited[i]) {
				DFS(i, visited);
			}
		}
	}
};

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int v, e;
	cin >> v >> e;
	Graph g(v);
	vector<bool> chk(v, false);
	int ans = 0;

	for (int i = 0; i < e; ++i) {
		int u, v;
		cin >> u >> v;
		g.addEdge(u-1, v-1);
	}

	for (int i = 0; i < v; ++i) {
		if (!chk[i]) {
			g.DFS(i, chk);
			ans += 1;
		}
	}
	cout << ans;
}