[BOJ 2606] S3 바이러스 C++

바이러스

난이도: Silver 3
번호: 2606
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

2606번: 바이러스

C++

#include <iostream>
using namespace std;

int N, P;
// 컴퓨터가 최대 100개 이므로 path도 최대 100 * 100
bool path[101][101];
bool visited[101];

void DFS(int S)
{
    visited[S] = true;

    for (int i = 1; i <= N; i++)
        if (!visited[i] && path[S][i])
            DFS(i);
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> P;

    for (int i = 0; i < P; i++)
    {
        int a, b;
        cin >> a >> b;
        path[a][b] = true;
        path[b][a] = true;
    }

    DFS(1);

    int cnt = 0;
    for (int i = 0; i <= N; i++)
        if (visited[i])
            cnt++;
    cout << cnt - 1;
}