(2606) 바이러스

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

단계별로 풀어보기

27단계(그래프와 순회) 5번째

 

 

 

DFS, BFS 둘 다 쓸 수 있다면 BFS를 선호한다.

재귀보다는 스택이 시간이나 에러 관리 측면에서 낫다 생각하기 때문이다.

사실 둘 다 써도 상관없을 정도의 난이도면 의미없을 가능성이 높지만.

 

 

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, ans= 0;
  
  cin >> n >> m;
  
  queue<int> q;
  vector adj(n+1, vector<int>());
  vector<bool> visited(n+1);
  
  while(m--){
    int u, v;
    
    cin >> u >> v;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  visited[1]= true;
  q.push(1);
  
  while(!q.empty()){
    int now= q.front();
    q.pop();
    
    for(int next:adj[now]){
      if(visited[next])  continue;
      
      visited[next]= true;
      ans++;
      q.push(next);
    }
  }
  
  cout << ans;
  
  return 0;
}