[백준] 알고리즘 11724번 - 연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
using namespace std;
int n, m;
vector<int> g[1001];
bool check[1001];
queue<int> qu;
void bfs(int index) {
	check[index] = true;
	qu.push(index);
	while (!qu.empty()) {
		int node = qu.front();
		qu.pop();
		for (int i = 0; i < g[node].size(); i++) {
			int next = g[node][i];
			if (check[next]) continue;
			check[next] = true;
			qu.push(next);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!check[i]) {
			bfs(i);
			ans++;
		}
	}
	cout << ans;
}

해설

연결요소란 한 정점이 이루는 그림이라 생각하면된다.

하나의 정점을 방문했을때 그릴 수 있는 그래프의 개수라고 생각하면된다.

https://github.com/kitten-master/algorithm/blob/master/graph/11724.cpp

GitHub - kitten-master/algorithm

dfs와 bfs를 구현해둔 소스입니다.

두개 참조하여 형태의 틀을 익히도록 하십시오.