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

백준 11724 연결 요소의 개수

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

• 그래프의 모든 정점을 방문하고자 할 때, DFS를 몇 번 호출해야하는지 세면 된다

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

int N, M;

vector<vector<int>> adj(1001);
vector<bool> visited;

void dfs(int here) {
	visited[here] = true;

	for (int i = 0; i < adj[here].size(); ++i) {
		int there = adj[here][i];
		if (!visited[there]) 
			dfs(there);
	}
}

int dfsAll() {
	visited = vector<bool>(N, false);

	//모든 정점이 방문될 때까지 dfs를 호출해야하는 횟수
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		if (!visited[i]) {
			dfs(i);
			++cnt;
		}
	}
	return cnt;
}

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

	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;

		adj[a - 1].push_back(b - 1);
		adj[b - 1].push_back(a - 1);
	}

	cout << dfsAll();
	return 0;
}

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

int n; //정점의 개수
int m; //간선의 개수

vector<vector<int>> adj(1000, vector<int>());


vector<bool> visited;

void bfs(int start) {
	queue<int> q;
	q.push(start);

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

		if (visited[cur]) continue;
		visited[cur] = true;

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

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

	cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u - 1].push_back(v - 1);
		adj[v - 1].push_back(u - 1);
	}

	visited.clear();
	for (int i = 0; i < n; ++i) {
		visited.push_back(false);
	}
	
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (!visited[i]) {
			bfs(i);
			ans++;
		}
	}
	cout << ans;
	return 0;
}

관련 문제

• 백준 4963 섬의 개수, 백준 2267 단지번호붙이기

• 이 문제들은 이전에 너비 우선 탐색(BFS)를 다룰 때 풀어본 적이 있다
  https://velog.io/@sunjoo9912/TIL-21-07-25#-bfs-%EC%98%81%EC%97%AD-%ED%83%90%EC%83%89

• 그래프의 모든 정점을 방문하고자 할 때 BFS를 몇 번 호출해야하는지 세면 그래프의 연결 요소의 개수를 구할 수 있다

📌 참고자료

• 그래프에서의 연결 요소(컴포넌트)의 개수 세기
  https://hy38.github.io/counting-the-components-of-graph

그래프의 연결 요소

• 무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 조각으로 쪼개져 있는 경우
  -> 각 연결된 정점들의 부분 집합 = 연결 요소 = 컴포넌트
• 그래프의 모든 정점 V를 방문하고자 할 때, DFS를 몇 번 호출해야하는지 세면 된다
  -> 그래프가 하나의 컴포넌트로 이루어져 있다면, 한 정점에서의 한 번의 DFS만으로 모든 정점을 방문할 수 있다
  -> 시간복잡도는 O(V + E)를 갖는다