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

 

1) 문제설명

백준 Online Judge 11724번 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

2) 아이디어

BFS를 사용하여 정점의 개수만큼 BFS를 실행하고 방문하지 않은 정점이 들어올 때마다 카운트를 증가시켜서 연결 요소의 개수를 구하였다. 

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

vector<int> v[1001];
int visited[1001];
int cnt = 0;
void bfs(int x) {
	if (visited[x] == 1) { // 방문했으면 돌아가
		return;
	}
	cnt++; // 연결되지 않은 새로운 그래프가 들어오면 연결요소추가
	queue <int> q;
	q.push(x);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			if (visited[v[x][i]] == 0) {
				q.push(v[x][i]);
				visited[v[x][i]] = 1;
			}
			
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	for (int i = 1; i <= n; i++) {
		
		bfs(i);
	}
	cout << cnt;
}