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

#11724 연결요소의 개수
https://www.acmicpc.net/problem/11724

✍연결 요소

: 한 개의 그래프가 여러 개의 그래프로 나뉠 수 있다.
이게 무슨 말이냐면,,,, 분명 하나의 그래프를 받았는데 떨어져 있는 정점이 존재할 수 있다는 거다

왼쪽은 문제에서 주는 첫 번째 예시를 그려본 것이다. 분명 저 둘은 하나의 그래프이지만 떨어져 있는 정점이 있다. 연결 요소가 2개인 그래프라고 말한다.

오른쪽은 그냥 그려봤다. 연결요소가 1개인 그래프이다.

📝문제 포인트

처음에 무조건 bfs로 방문여부를 표시해주게 된다. 만약 연결요소가 1개인 그래프라면 모든 점을 다 방문했을 것이다. 1개 이상이면 방문 되지 않은 정점도 존재할 것이다. 그 때 count의 개수를 증가시켜주면 된다

✍코드

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 1001
using namespace std;

int n, m;
int a, b;
int map[MAX][MAX];
int visited[MAX];
queue<int>q;

void bfs(int v) {
	visited[v] = 1;

	q.push(v);

	while (!q.empty()) {
		v = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (map[v][i]  && visited[i]==0) {
				q.push(i);
				visited[i] = 1;
			}
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		map[a][b] = map[b][a] = 1;
	}
	
	int count = 0;
	for (int i = 1; i <=n; i++) {
		if (visited[i] == 0 ) {
			bfs(i);
			count++;
		}
	}
	cout << count;
}