A - Reachable Towns

• Quiz
  • https://atcoder.jp/contests/acl1/tasks/acl1_a
• AC
  • https://atcoder.jp/contests/acl1/submissions/16925269
• 解説
  • (x,y)の昇順にソートする
  • 順に見ていって、必要ならunion findでmergeする
  • 愚直にやるとTLEするが、連結成分ごとにyの最小値を持っておけば十分なことに気づくと、merge回数はO(N)に抑えられる

（画像、同じYが存在するのは見逃してください＞＜）

#include <atcoder/dsu>
using namespace atcoder; // 忘れがち

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    auto uf = dsu(N);

    VI X(N);
    VI Y(N);
    VI Ix(N);
    VI Iy(N);

    rep(i,N){
      ll x,y;cin>>x>>y;
      x--;y--;
      
      X[i]=x;
      Y[i]=y;
      Ix[x]=i;
      Iy[y]=i;
    }
    
    vector<PII> V;
    rep(i,N){
      V.push_back({X[i],Y[i]});
    }
    sort(ALL(V));

    set<ll> se;
    rep(i,N){
      ll x=V[i].first;
      ll y=V[i].second;

      if(se.size()==0){
        se.insert(y);
        continue;
      }

      if(*se.begin()>y){
        se.insert(y);
        continue;
      }

      VI temp;
      // yより小さいものと統合
      for(ll a : se){
        if(a<y){
          temp.push_back(a);
        }else{
          break;
        }
      }
      // 一番小さいyをsetに入れる
      ll mi = y;
      chmin(mi, MIN(temp));
      se.insert(mi);
      // unite
      ll my_idx = Iy[y];
      for(ll v : temp){
        ll idx = Iy[v];
        uf.merge(my_idx, idx);
      }
    }

    rep(i,N){
      ll sz = uf.size(i);
      p(sz);
    }
    
    return 0;
}