(24445) 알고리즘 수업 - 너비 우선 탐색 2

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

단계별로 풀어보기

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

 

 

 

#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, r, x= 1;
  
  cin >> n >> m >> r;
  
  queue<int> q;
  vector adj(n+1, vector<int>());
  vector<int> visited(n+1);
  
  while(m--){
    int u, v;
    
    cin >> u >> v;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  for(int i=1;i<=n;i++)  sort(adj[i].begin(), adj[i].end(), greater<int>());
  
  auto bfs= [&](int start) -> void {
    visited[start]= x++;
    q.push(start);
    
    while(!q.empty()){
      int now= q.front();
      q.pop();
      
      for(int next:adj[now]){
        if(visited[next])  continue;
        
        visited[next]= x++;
        q.push(next);
      }
    }
  };
  
  bfs(r);
  
  for(int i=1;i<=n;i++)  cout << visited[i] << "\n";
  
  return 0;
}