백준 BaekJoon (바이러스, 2606) C++

 

BFS 로 간단하게 사이클에 visited하게 되는 node가 몇 개인지 세어주면 된다.

 

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

using namespace std;

int main() {
    int computer = 0;
    int num = 0;

    cin >> computer;
    cin >> num;

    vector<vector<int>> adj(computer+1);
    vector<int> visited(computer, 0);
    queue<int> q;

    for(int i = 0 ; i < num ; i++) {
        int one = 0, two = 0;
        cin >> one >> two;

        adj[one].push_back(two);
        adj[two].push_back(one);
    }

    // for(int i =1 ; i < adj.size() ; i++) {
    //     cout << "[ " << i << " ] ";
    //     for(int j =0  ; j < adj[i].size() ; j++) {
    //         cout << adj[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    int connected = 0;

    q.push(1);
    visited[1] = 1;

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

        for(int i = 0 ; i < adj[node].size() ; i++) {
            if(visited[adj[node][i]] == 0) {
                connected++;
                visited[adj[node][i]] = 1;
                q.push(adj[node][i]);
            }
        }
    }

    cout << connected ;

    return 0;
}