[PS] 백준 2606번 - 바이러스

연결리스트로 표현한 후에 BFS를 이용하여 감염시키고 카운트를 올린다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int cnt=0;
vector<int> graph[101];
bool infect[101];

void BFS() {
    memset(infect, false, sizeof(infect));
    queue<int> q;
    q.push(1);
    infect[1]=true;

    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0; i<graph[now].size(); i++) {
            int next=graph[now][i];
            if(!infect[next]) {
                q.push(next);
                infect[next]=true;
                cnt++;
            }
        }
    }
    cout << cnt;
}

int main(void) {
    int n, v;
    cin >> n;
    cin >> v;
    for(int i=0; i<v; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for(int i=1; i<n; i++) sort(graph[i].begin(), graph[i].end());
    BFS();
    return 0;
}