🤦‍♀️백준 2606 (바이러스/그래프)

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

그래프 자료구조를 잘 모른다. 글을 봤는데 이해가 안되는 부분들이 있어서 나의 멘탈 관리를 위해 일단 이 문제를 풀기위한 지식들까지만 이해했다.

문제이해

일단 1번의 컴퓨터가 바이러스에 감염된다고 했을 때, 바이러스가 전염되어서 총 몇 대의 컴퓨터가 감염되는 지 구하는 문제이다.
저절로
이런 그림이 머리에 그려진다.
1) 그래프란 정점과 간선으로 이루어진 자료구조이다
2) 해당 문제는 방향성이 없다.
라는 사실을 일단 알아낸다.

이제 인접 행렬로 생각할 지 인접 리스트로 생각할 지 정해야 한다.
인접 행렬을 사용하도록 추천하는 경우는 : 간선이 정점^2와 가까울 때이다.
인접 리스트를 사용하도록 추천하는 경우는 위의 반대이다.
문제에서 정접은 100까지 올 수 있고 간선은 따로 내용이 주어지지 않았다.

간접 리스트를 사용해 보도록 하겠다. 무방향 그래프이기 때문에 각각의 정점이 인접되어 있는 정점을 그림으로 그리면
1) 2, 5
2) 1, 3, 5
3) 2
4) 7
5) 1, 2, 6
6) 5
7) 4
이다. 주어진 예를 기준으로 풀이하였다.
1번은 2번 5번과 연결되어 있다.
그럼 우선적으로 2번을 들어간다. 2번은 다시 1, 3, 5와 연결되어 있다. 1은 포함하지 않는다. 3과 연결되어 있다.
3으로 들어간다. 3은 2와 연결되어 있다. 2는 이미 count하였기 때문에 세지 않는다. 3이 끝난다.
다시 2로 돌아간다. 그 다음은 5이다.
5로 들어간다 1, 2 모두 이미 count되었기 때문에 세지 않는다. 6으로 넘어간다
6으로 들어왔다. 5는 이미 세었다 돌아간다
5로 돌아왔다. 다시 2로 돌아간다.
2로 돌아왔다 다시 1로 돌아간다
...
재귀가 반복된다.

이를 코드로 작성하면 아래와 같이 나올 것이다.
이때의 시간 복잡도를 계산해보면 O(ve)인 것 같다

code

#include <bits/stdc++.h>
using namespace std;
int cnt;
int visited[101];
vector<int> vec[101];

void    round(int n)
{
    cnt++;
    visited[n] = 1;

    for (int i = 0; i < vec[n].size(); i++)
    {
        if (!visited[vec[n][i]])
            round(vec[n][i]);
    }
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    int v, e;
    cin >> v >> e;

    vec->resize(v + 1);

    while (e--)
    {
        int num1, num2;
        cin >> num1 >> num2;
        vec[num1].push_back(num2);
        vec[num2].push_back(num1);
    }

    round(1);
    cout << cnt - 1;
    return (0);
}