백준 2606 (C++) - 바이러스 (BFS, DFS)

ㅠㅠ 나 그래프 영원히 못풀줄 알았는데...... 이제 이해했다.... 

DFS, BFS 로 모두 풀어봤다.

main 함수에서 원하는걸로 주석 처리하면된다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;

#define MAX 101

vector<int> graph[MAX];
int visited[MAX];
int cnt = -1;

void bfs(int r) {
    deque<int> qq;
    visited[r] = 1;
    qq.push_back(r);
    while(!qq.empty()) {
        int tmp = qq.front();
        qq.pop_front();
        cnt++;
        for(int i = 0; i < graph[tmp].size(); i++) {
            int y = graph[tmp][i];
            if(!visited[y]) {
                visited[y] =1;
                qq.push_back(y);
            }
        }
    }
}

void dfs(int r) {
    if(visited[r] == 1) return;
    visited[r] = 1;
    cnt++;
    for(int i = 0; i < graph[r].size(); i++) {
        int tmp = graph[r][i];
        dfs(tmp);
    }

}

int main() {
    int cpu, pair;
    scanf("%d", &cpu);
    scanf("%d", &pair);
    for(int i = 1; i <= pair; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    //bfs(1);
    dfs(1);
    printf("%d\n", cnt);

    return 0;
}