[백준 2606][C++] 바이러스 (Silver 3)

[문제보기]

 2606. 바이러스

2606번: 바이러스

 

[풀이과정]

vector를 사용하여 트리를 형성해준 후 BFS 알고리즘을 사용하여 1번 컴퓨터와 연결된 컴퓨터를 찾았다.

 

[소스코드]

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

using namespace std;

int n, m, ans = 0;
bool visit[101];
vector<vector<int>> v;
queue<int> q;

void BFS(){
    while(!q.empty()){
        int node = q.front();
        q.pop();

        for(int i=0; i<v[node].size(); i++){
            int next = v[node][i];
            if(!visit[next]){
                visit[next] = true;
                q.push(next);
                ans++;
            }
        }
    }
}

int main(){
    cin >> n >> m;
    v = vector<vector<int>>(n+1, vector<int>());

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    q.push(1);
    visit[1] = true;
    BFS();

    cout << ans;
}