(c++)백준 11724번: 연결 요소의 개수

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

11724번: 연결 요소의 개수

[풀이]

연결 요소 : 한 개 이상의 간선으로 연결된 정점들로 이루어진 그래프.(서로 아무 관련 없는 각각의 그래프)

연결 요소 조건

- 연결 요소에 속한 모든 정점을 잇는 경로가 존재해야 함.

- 다른 연결 요소에 속하는 정점과 이어지는 경로가 있으면 안됨.

 

방문을 체크하는 배열을 만들어서 체크하지 않은 정점을 시작점으로 bfs를 돌린다.

bfs를 돌린 횟수가 연결요소의 개수이다.

 

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

int N, M;
int Graph[1001][1001] = { 0, };//정점 연결되어 있으면 1
bool check[1001] = { false, };

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		Graph[u][v] = 1;
		Graph[v][u] = 1;
	}
}

void bfs(int start) {
	queue<int>q;
	q.push(start);
	check[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {
			if (Graph[cur][i] == 1 && check[i] == false) {
				check[i] = true;
				q.push(i);
			}
		}
	}
}

void solution() {
	input();
	int cnt = 0;//연결 요소 개수
	for (int i = 1; i <= N; i++) {
		if (check[i] == false) {
			bfs(i);
			cnt++;
		}
	}
	cout << cnt << endl;
}

int main() {
	solution();
	return 0;
}