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; }