바이러스 2606

문제

접근 방법

양방향 그래프로 생각하고 풀면 된다.
1에서 시작하여 다른 정점으로 간 뒤 Bool 배열을 true로 해주어 중복방문 안 하게 해주면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, ret = 0;
    cin >> N >> M;
    vector<vector<int>> map(N + 1, vector<int>());
    vector<bool> isVisted(N + 1);
    queue<int> bfs;
    while (M--)
    {
        int n1, n2;
        cin >> n1 >> n2;
        map[n1].push_back(n2);
        map[n2].push_back(n1);
    }
    bfs.push(1);
    isVisted[1] = true;
    while (!bfs.empty())
    {
        int cur = bfs.front();
        bfs.pop();
        for (int next : map[cur])
        {
            if (isVisted[next])
                continue;
            isVisted[next] = true;
            ++ret;
            bfs.push(next);
        }
    }
    cout << ret;
    return 0;
}

풀이

BFS, DFS 둘 다 사용이 가능할 것이다.
분리된 공간에서 정점이 몇 개 있는지 확인하는 문제이다.