[백준/C,C++] 2606번: 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

풀이

1번을 기준으로 DFS나 BFS를 돌려주기만 하면 되는 문제입니다.

 

#include<iostream>
#include<vector>

using namespace std;

const int MAX = 101;

vector<int> v[MAX];
bool visited[MAX];
int res = -1;

void DFS(int node)
{
    res++;
    visited[node] = true;
    size_t sz = v[node].size();

    for (size_t i = 0; i < sz; i++) {
        int next = v[node][i];
        if (!visited[next]) DFS(next);
    }

    return;
}

int main(void)
{
    int n, m; cin >> n >> m;

    while (m--) {
        int i, j; cin >> i >> j;
        v[i].push_back(j);
        v[j].push_back(i);
    }

    DFS(1);

    cout << res;

    return 0;
}

반례

Input

2

1

1 2

Output

1

 

Input

8
7
1 2
2 3
3 4
4 1
5 6
6 7
7 8

Output

3