https://www.acmicpc.net/problem/2606

• 문제 설명

컴퓨터의 개수와 컴퓨터가 연결된 쌍이 입력으로 주어진다. 1번 컴퓨터가 바이러스에 감염되었다고 가정했을 때, 바이러스에 감염된 컴퓨터의 수를 출력한다.

• 문제 풀이

컴퓨터로 연결된 쌍, 즉 그래프의 연결이 주어졌을 때 그 그래프에 연결된 컴퓨터의 개수를 찾으면 되는데, 이를 DFS로 해결했다.

• 정답 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;

vector<int> graph[101010];
int virus[101010];
int visited[101010];

int cnt = 0;

void dfs(int start){
    for(int i = 0; i < graph[start].size(); i++){
        int x = graph[start][i];
        if(virus[x] == 0){
            virus[x] = 1;
            cnt++;
            dfs(x);
        }
    }
}

int main() {
    FASTIO;

    int n; cin >> n;
    int t; cin >> t;
    while(t--){
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    virus[1] = 1;
    dfs(1);

    cout << cnt << '\\n';

    return 0;
}