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

 

 

 

 

 

BFS와 DFS 두가지를 모두 이용하여 풀수 있는 문제다.

 

 

 

1. DFS

#include <iostream>
#include <queue>
#include <cstring> //memset
#include <vector>
using namespace std;

const int MAX = 1000 + 1;

int N, M;
vector<int> connect[MAX];	// 이차가됨
bool visited[MAX];

void DFS(int node) {

	visited[node] = true;

	// node에 연결된 다른 정점을 모두 방문
	for (int i = 0; i < connect[node].size(); i++) {	
		int next = connect[node][i];

		if (!visited[next]) {
			DFS(next);
		}
	}
	
}


int main(void) {
	
	cin >> N >> M;

	int u, v;

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;

		connect[u].push_back(v);
		connect[v].push_back(u);
	}

	int cnt = 0; 
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			DFS(i);
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}

 

 

 

 

2. BFS

#include <iostream>
#include <queue>
#include <cstring> //memset
#include <vector>
using namespace std;

const int MAX = 1000 + 1;

int N, M;
queue<int> q;
vector<int> connect[MAX];
bool visited[MAX];

void BFS(int node) {
	visited[node] = true;

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

		// cur와 연결된 모든 노드를 방문
		for(int i = 0; i < connect[cur].size(); i++) {

			int next = connect[cur][i];

			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
	
}


int main(void) {
	
	cin >> N >> M;

	int u, v;

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;

		connect[u].push_back(v);
		connect[v].push_back(u);
	}

	int cnt = 0; 
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			q.push(i);
			BFS(i);
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}