[BOJ 2606 / C++] 바이러스 (그래프)

문제링크: https://www.acmicpc.net/problem/2606

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>>& adj, vector<bool>& vis, int cur, int& cnt) {
    vis[cur] = true;
    cnt++;
    for (int nxt: adj[cur]) {
        if (vis[nxt]) continue;
        dfs(adj, vis, nxt, cnt);
    }
}

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n+1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> vis(n+1, false); 
    int cnt = 0;
    dfs(adj, vis, 1, cnt);
    cout << cnt-1;
}

 

 

2. 시간복잡도

정점의 개수 v = 100이고, 간선의 개수 e = 최대 v(v-1)/2 = 50*90 = 4500이다. 인접리스트에서 dfs, bfs의 시간복잡도는 O(v+e)이므로 4600 < 10^8 으로 시간제한 1초 안에 해결 가능하다.

 

 

3. 분석

인접리스트로 그래프를 입력받고 dfs로 순회하면서 연결되어있는 노드의 개수를 세면 된다. 1번 노드가 감염시킨 노드의 개수를 세야하므로 첫번째 노드인 1개를 빼줘야한다.