(1260) DFS와 BFS

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

단계별로 풀어보기

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

 

 

 

한 문제에서 그래프 탐색을 두 번 이상 해야 할 땐 초기화에 주의해야 한다. 제대로 하지 않으면 두 번째 이후의 탐색이 제대로 되지 않을 수 있다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, v, x= 1;
  
  cin >> n >> m >> v;

  vector adj(n+1, vector<int>());
  vector<bool> visited(n+1);
  
  while(m--){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  
  for(int i=1;i<=n;i++)  sort(adj[i].begin(), adj[i].end());
  
  auto dfs= [&](auto self, int now) -> void {
    cout << now << " ";
    visited[now]= true;
    
    for(int next:adj[now]){
      if(visited[next])  continue;
      
      self(self, next);
    }
  };
  
  dfs(dfs, v);
  cout << "\n";
  
  queue<int> q;
  visited= vector<bool> (n+1);
  
  visited[v]= true;
  q.push(v);
  
  while(!q.empty()){
    int now= q.front();
    q.pop();
    cout << now << " ";
    
    for(int next:adj[now]){
      if(visited[next])  continue;

      visited[next]= true;
      q.push(next);
    }
  }
  
  return 0;
}