[C++]伯俊-#2066:ウイルス

問題の説明

入力

しゅつりょく

解法
久しぶりのBFS問題です.
他のBFS問題とは異なり,ノード間の接続を確認するだけである.
入力として与えられたboard[]]の対応するインデックスの値を1に変更します.
スタートは1番コンピュータからなので、BFSで使用しているqueueにまず1を入れます.
また、1番コンピュータはウイルス感染状態にあり、vis[1]も1に変換した.
その後、VIS[i]=0をVIS[i]に変換し、VIS[i][i]=1をキューに押し込む(この問題ではウイルスに感染したか否かを意味する).
以上の手順でboardのすべてのセルに対して実行すると、正しい答えが得られます.そして得られた答えから1を取り除く.質問の中で1番パソコン以外の他のパソコンが正解を聞いているからです.
ソースコード

#include <bits/stdc++.h>
using namespace std;

int board[101][101];
bool vis[101];
int n, m;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int a, b;
	int cnt = 0;

	queue <int> q;
	q.push(1);
	vis[1] = 1;

	cin >> n;	
	cin >> m;

	for (int i = 0; i < m; i++)
	{
			cin >> a >> b;
			board[a][b] = 1;
			board[b][a] = 1;
	}


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

		cnt++;

		for (int i = 1; i <= n; i++)
		{
			if (board[cur][i] == 1 && vis[i] == 0)
			{
				vis[i] = 1;
				q.push(i);
			}
		}
	}

	cout << cnt - 1;
	
}

フィードバック
BFSを解くのは久しぶりですが、やっぱり難しいです.
数学の公式を暗記するようにBFSを暗記して実現しますか?やるというより、問題の条件に合わせて実施することが大切です.
また,ほとんどのBFS／DFS問題と同様に,どちらかしか使用できないケースはほとんどない.DFSを調べてみると再帰関数として多く実現されているようです.これまでBFSは比較的便利だった.