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

[문제 링크]

11724번: 연결 요소의 개수

---

문제를 풀기 전에 연결 요소가 뭔지 알아야 할 필요가 있다.

연결 요소란? 그래프에서 하나로 연결된 정점들의 집합이라고 생각하면 된다.

 

그래프의 모든 정점을 방문할 때 까지 bfs나 dfs를 수행한 다음, 수행한 횟수가 곧 연결 요소의 갯수가 된다.

정점의 개수가 많고 양방향 그래프로 표현해야 하기 때문에 인접 행렬보단 인접 리스트로 그래프를 구현하는 것이 효율적이고 직관적이라고 생각한다.

---

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

int N, M;
vector<int> adj[1001];
bool visited[1001];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

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

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i];
			
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

int getConnectedComponent() {
	int result = 0;

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

	return result;
}

int main(void) {
	cin >> N >> M;

	// 양방향 그래프로 구현할 것
	while(M--) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cout << getConnectedComponent() << endl;

	return 0;
}