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

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

11724번: 연결 요소의 개수

<코드>

이 문제는 dfs, bfs의 기본 문제이다. 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#define max 1001

int board[max][max];
bool visited[max] = {0};
int cnt=0;
int n,m;


using namespace std;
//void dfs(int node)
//{
//	visited[node] = true;
//	for(int i=1;i<=n;i++)
//		if(!visited[i] && board[node][i]){
//			dfs(i);
//		}
//}
void bfs(int node)
{
	queue<int>q;
	visited[node] = true;
	q.push(node);
	while(!q.empty())
	{
		int cur = q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(!visited[i] && board[cur][i]==1)
			{
				visited[i] = true;
				q.push(i);
			}
		}
	}
}
int main()
{
	memset(board,0,sizeof(board));
	int u,v;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v;
		board[u][v] = board[v][u] = 1;
	}

	for(int i=1;i<=n;i++){
		if(!visited[i]){
			cnt++;
			//dfs(i);
			bfs(i);
		}
	}
	cout<<cnt;
	
}

<풀이과정>

방문여부가 false이고 간선이 존재하면 탐색을 진행하는 방향으로 알고리즘을 설계하였다.

dfs는 재귀적으로 해결하였고, bfs는 각 방문여부를 true로 바꿔주고 각 정점을 push하는 과정으로 해결하였다.