PAST E - 順列

• Quiz
  • https://atcoder.jp/contests/past202004-open/tasks/past202004_e
• AC
  • https://atcoder.jp/contests/past202004-open/submissions/17899410
• 解説
  • 制約が緩いのでシミュレーションしてもいいけれど、連結成分のサイズでも求められる

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

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

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N){
      cin >> A[i];
      A[i]--;
    }

    dsu uf(N);

    rep(i,N){
      uf.merge(i,A[i]);
    }

    VI Ans;
    rep(i,N){
      ll ans = uf.size(i);
      Ans.push_back(ans);
    }
    print_vector(Ans);
    
    return 0;
}