AtCoder Regular Contest 056 B - 駐車場

問題概要

リンク

略

解法

• ある車xに着目する時、あるエッジの両端u,vについて、min(u,v) >= xの時、その道にまだ車が止まっていないため通行可能である
• 通行可能な道をUnion Findでマージし、same(S, x)がtrueとなれば到達可能である
• この制約はxが大きくなるほど厳しくなるため、エッジをmin(u, v)が大きい順にソートし、大きい車から順番に見ていく

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

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

struct UnionFind{
    vector<int> parents;
    vector<int> rank;
    UnionFind(int n){
        parents.resize(n);
        rank.assign(n, 1);
        REP(i, n){
            parents[i] = i;
        }
    }
    int find(int x){
        if(parents[x] == x) return x;
        return parents[x] = find(parents[x]);
    }
    
    int unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return -1;
        if(rank[x] > rank[y]) parents[y] = x;
        else{
            parents[x] = y;
            if(rank[x]==rank[y]) rank[y]++;
        }
        return 0;
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

#define MAX_N 200010
int N, M, S;
p t[MAX_N];
int main(){
    ios::sync_with_stdio(false);
    cin >> N >> M >> S;
    S--;
    REP(i,M) {
        int u,v;
        cin >> u >> v;
        u--;v--;
        t[i].first=min(u,v);
        t[i].second=max(u,v);
    }
    sort(t,t+M,greater<p>());
    UnionFind uf(N);
    int cur=0;
    vector<int> ans;
    for (int i = N-1; i >= 0; i--) {
        while(cur<M) {
            if(t[cur].first>=i) {
                uf.unite(t[cur].first, t[cur].second);
                cur++;
            }
            else break;
        }
        if (uf.same(S,i)) ans.pb(i);
    }
    reverse(all(ans));
    for(auto x: ans) {
        cout << ++x << endl;
    }
    
    return 0;
}