백준 알고리즘 2606번 : 바이러스

링크

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

sol1) DFS in graph

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

vector<int> adj[101];
bool vist[101];
int oneComponent = 0;

void dfs(int cur){
  vist[cur] = true;
  for(auto nxt : adj[cur]){
    if(vist[nxt]) continue;
    oneComponent++;
    dfs(nxt);
  }
}

int32_t main() {
  fastio;
  int n,m; cin >> n >> m;
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1);
  cout << oneComponent << "\n";
}

그래프 안에서 dfs를 탐색하고 1을 포함한 컴포넌트 안에 속해 있는 정점들의 갯수를 구해주면 됩니다.