ARC 056-B 駐車場

ARC056B.cpp

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
typedef pair<int, int> pii;
vector<int> g[2*100000];
 
int main(){
 
   int N, M, s;
   cin>> N>> M>> s;
   s--;
 
   for(int i=0; i<M; i++){
      int a, b;
      cin>> a>> b;
      a--; b--;
      g[a].push_back(b);
      g[b].push_back(a);
   }
 
   priority_queue<pii> Q;
   Q.push(pii(s, s));
   int cost[N];
   fill(cost, cost+N, 0);
   cost[s]=s;
   while(!Q.empty()){
      int c, i;
      c=Q.top().first;
      i=Q.top().second;
      Q.pop();
      for(int j: g[i]){
         int _c=min(c, j);
         if(_c>cost[j]){
            cost[j]=_c;
            Q.push(pii(_c, j));
         }
      }
   }
 
   for(int i=0; i<N; i++){
      if(cost[i]>=i) cout<< i+1<< endl;
   }
 
   return 0;
}