백준 - 2606 바이러스

 

 

2606번: 바이러스

본 문제는 BFS 를 통해 첫번째 노드와 인접한 모든 노드들을 세면 되는 간단한 문제 이다.

코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int nrNode, nrEdge;

	cin >> nrNode >> nrEdge;
	vector<vector<int>> nw(nrNode + 1, vector<int>(nrNode + 1, 0));

	int t1, t2;
	for (int i = 0; i < nrEdge; i++)
	{
		cin >> t1 >> t2;
		nw[t1][t2] = 1;
		nw[t2][t1] = 1;
	}

	vector<int> visit(nrNode + 1, 0);

	int start = 1;
	visit[start] = 1;

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

	int result = 0;

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

		for (int i = 1; i <= nrNode; i++)
		{
			if (nw[qd][i] && visit[i] == 0)
			{
				visit[i] = 1;
				q.push(i);
				result++;
			}
		}
	}
	cout << result << endl;
}