[백준] 바이러스

문제 링크

 

풀이

1번 컴퓨터에 연결된 노드의 갯수만 구하면 된다. 카운트할 때 1번 컴퓨터는 제외한다. 예를 들어 1번, 2번이 감염됐다면 카운트는 1이다. 큐를 이용해 bfs로 풀 수 있다. 1번 컴퓨터가 다른 컴퓨터와 연결되어 있지 않다면 0이 출력되면 된다.

 

코드

#include <queue>
#include <cstdio>
using namespace std;
int main()
{
	int N, pair;
	bool visited[101] = {};
	scanf("%d%d", &N, &pair);
	++N;
	int com[101][101] = {};
	for (int i = 0; i < pair; ++i)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		com[a][b] = 1;
		com[b][a] = 1;
	}
	
	queue<int> q;
	q.push(1);
	visited[1] = true;
	int answer = -1;
	while (!q.empty())
	{
		auto n = q.front();
		q.pop();
		++answer;
		for (int i = 1; i <= N; ++i)
		{
			if (com[n][i] && !visited[i])
			{
				visited[i] = true;
				q.push(i);
			}
		}
	}
	printf("%d\n", answer);
}