백준 2606 - 바이러스

웜 바이러스는 네트워크 망을 통해 감염시키는 바이러스입니다.
그래프 형태의 컴퓨터 통신망이 주어졌을 때, 1번 컴퓨터가 감염될 경우 감염되는 컴퓨터의 개수를 구하는 문제입니다.

Undirected Graph Traversal을 통해 해결할 수 있습니다.

탐색 방식은 BFS, DFS 상관없어보였으며, Undirected Graph로 구현하는 것이 중요합니다.
저는 BFS 방식으로 구현했습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <deque>

int main()
{
	int compCnt, adjCnt;
	std::cin >> compCnt >> adjCnt;

	std::vector<std::set<int>> adjList;
	std::vector<int> compList;

	for(int i = 1; i <= compCnt; i++)
	{
		compList.push_back(i);
	}

	adjList.resize(compList.size() + 1);

	for (int i = 0; i < adjCnt; i++)
	{
		int comp1, comp2;
		std::cin >> comp1 >> comp2;
		adjList[comp1].insert(comp2);
		adjList[comp2].insert(comp1);
	}

	std::vector<bool> closed(compList.size() + 1);
	std::deque<int> open;

	open.push_back(compList[0]);
	int cnt = -1;
	while (!open.empty())
	{
		int n = open.front();
		closed[n] = true;
		cnt++;
		open.pop_front();

		for (int adj : adjList[n])
		{
			if (!closed[adj] && std::find(open.begin(), open.end(), adj) == open.end())
				open.push_back(adj);
		}
	}

	std::cout << cnt;

	return 0;
}