AtCoder Regular Contest 056 駐車場

昔のARCもちゃんと埋めていこうと思います。

問題概要

無向グラフが与えられる。人i(1 <= i <= N)は始点Sから出発して、自分より小さい番号の頂点を通らずに頂点iまで到達できるだろうか？到達できる番号を全て列挙せよ。

頂点数、辺数共に2e5以下。

解法

解説PDFをなぞるような形になりますが、実装も示します。

頂点Sから頂点 i まで、iより大きい辺のみを通って行けるパスが存在することが、人iが頂点iに到達できることの必要十分条件です。グラフは木とは限らないので、パスは一通りではなく複数あり得ます。人iがあるパスを通って頂点iにたどり着けるかを決定するのは、そのパス中で最小の番号の頂点です。ここで、人iはSからiまでのパスのうち、最小の番号が最も大きいパスを選ぶことが最適であることがわかります。

cost[i] を、始点Sから頂点iまでのパス中の最小番号としてあり得るものの最大値、とします。

cost[s] = sに注意します。「人iが頂点iにたどり着ける」 ⇔ (cost[i] >= i)です。

さて、cost[i]は頂点Sから出発したDIjkstra法と同様のアルゴリズムで、cost[i]が大きい頂点から順番に決定することができます。現在未確定のcostのうち、最大のcostは他のcostによってより大きくなることがあり得ないからです。

実装は次の通りです。

// solution for ARC056B
// author : lynmisakura

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i,n) for(int (i) = 0;(i) < (n);(i)++)

const int maxn = 200020;

int n,m,s;
vector<int> g[maxn];

void read(){
  cin >> n >> m >> s;
  s--;
  REP(i,m){
    int u,v;cin >> u >> v;
    u--,v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
}

int cost[maxn];

int main(int argc, char const *argv[])
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  read();

  REP(i,n) cost[i] = -1;
  cost[s] = s;

  priority_queue<pair<int,int>> q; // {cost,index}  
  cost[s] = s;
  q.emplace(s,s);

  while(q.size()){
    
    int c = q.top().first;
    int v = q.top().second;
    q.pop();

    int newcost = min(cost[v] , v);

    for(int i : g[v]){
      if(newcost > cost[i]){
        cost[i] = newcost;
        q.emplace(newcost,i);
      }
    }

  }

  REP(i,n){
    if(cost[i] >= i)cout << i+1 << '\n';
  }

  return 0;
}