BaekJoon 11724 연결 요소의 개수 (BFS)

 

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

소스 결과 : 7124 KB / 256 ms

 

소스 설명

백준 11724 연결 요소의 개수 BFS 버전

알고리즘은 DFS와 동일

 

DFS 버전 : https://girlfriend-yerin.tistory.com/13

 

소스 코드

#include <iostream>
#include <queue>

using namespace std;

bool adjMatrix[1000][1000];
bool check[1000];

int main()
{
	int n, m, count = 0;
	int startNum = -1;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;

		adjMatrix[x - 1][y - 1] = adjMatrix[y - 1][x - 1] = true;
	}

	for (int i = 0 ;i < n ; i++)
	{	
		if (check[i])
			continue;

		queue<int> q;
		q.push(i);

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

			if (check[cur])
				continue;

			check[cur] = true;

			for (int j = 0; j < n; j++)
			{
				if (adjMatrix[cur][j])
					q.push(j);
			}
		}

		count++;
	}

	cout << count;

	return 0;
}