ARC 056 B - 駐車場

問題

問題概要

s->iへ到達できるか。ただし、通れる頂点に制約あり。

解法

思いついたのは、逆からunion-find。頂点iに行けるかを見る場合、i以上の頂点を使い、sからiへたどり着けるかを見れば良いので、i=n-1からi=0の順に調べ、そのつど、追加できる辺を追加しながら、union-findで、sとiが同じグループに属しているかを調べていけばいい。 追加できる辺は、iとつながる頂点のみを見て、iより大きければ、その辺を追加していくようにすればいい。このように追加していけば、両端がi以上の頂点で作られている辺は全て追加したことになる。
公式解説によると、ダイクストラ風でやるみたい。いつもは距離の最小値を入れているが、今回は、その頂点に到達するために、通る頂点の最小値をいれ、最小値の最大が求まるようにすればいいみたい。思いつかない。

ミス

ダイクストラを応用するのも練習しておかなければ、

コード

逆からunion-find

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

class DisjointSet{
    public:
        vector<int> rank, p;//rank:木の高さ p:親の頂点番号
        DisjointSet(){}
        DisjointSet(int size){//頂点の数
            rank.resize(size, 0);
            p.resize(size, 0);
            rep(i, size) makeSet(i);
        }
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }
        bool same(int x, int y){return findSet(x) == findSet(y);}
        void unite(int x, int y){link(findSet(x), findSet(y));}
        void link(int x, int y){
            if(rank[x] > rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x] == rank[y]) rank[y]++;
            }
        }
        int findSet(int x){
            if(x != p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};

vector<int> g[200010], ans;
int main(void){
    int n, m, s; 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);
    }
    DisjointSet uf(n);
    //逆からunion-find
    //i番目の頂点に到達できるか考える時は、iより大きい頂点だけで作られる、グラフを作り、
    //sとiから同じ連結成分に含まれるかを調べればいい。
    for (int i = n - 1; i >= 0; --i){
        for(auto j : g[i]){
            if(j >= i){//iより大きい頂点と繋がっている道は追加
                uf.unite(i, j);
            }
        }
        if(uf.same(s, i)) ans.push_back(i);
    }
    reverse(ans.begin(), ans.end());
    rep(i, ans.size()){
        cout << ans[i] + 1 << endl;
    }
    return 0;
}

ダイクストラ風?

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

const int MAX_N = 200010;
int n, m; //町の数 道路の本数
int s;
vector<int> g[MAX_N];//グラフを表す隣接リスト
int d[MAX_N]; //d[i] := sからiに至るまでに通る道の中で、頂点番号の最小を一番大きくした時の頂点番号
typedef pair<int, int> P;//firstは最短距離,secondは頂点の番号

//今回はコストの大きい頂点から決めていく
void dijkstra(void){
    priority_queue<P> que;//firstが大きい順に
    rep(i, n) d[i] = -1;//初期化
    d[s] = s;
    que.push(make_pair(s, s));//fi: 巡ってきた最大頂点番号 se:今の頂点番号
  
    while(!que.empty()){
        auto p = que.top(); que.pop();
        int v = p.second;
        for(auto u : g[v]){//u:隣接している頂点の番号
            int t = min(d[v], u);
            if(d[u] < t){//が更新されるとき
                d[u] = t;
                que.push(make_pair(d[u], u));
            }
        }
    }
}

int main(void){
    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);
    }
    dijkstra();
    rep(i, n){
        if(d[i] >= i) cout << i + 1 << endl;
    }
    return 0;
}