結果

問題 No.3650 Teleportation Cycles
コンテスト
ユーザー kukone
提出日時 2026-08-28 21:50:39
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 188 ms / 2,000 ms
+ 690µs
コード長 2,014 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,818 ms
コンパイル使用メモリ 382,456 KB
実行使用メモリ 50,552 KB
最終ジャッジ日時 2026-08-28 21:50:48
合計ジャッジ時間 7,517 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using P=pair<ll,ll>;
typedef atcoder::modint mint;
ll inf=9e18;
template<class... T>
constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
template<class... T>
constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<typename T, int s, int i = 0>
auto vec(const ll (&sizes)[s], const T& init = T()){
  if constexpr(i < s) return vector(sizes[i], vec<T, s, i+1>(sizes, init));
  else return init;
}

void tp_dfs(vector<vector<ll>> &v,vector<bool> &q,ll s,stack<ll> &sorted){
  q[s]=0;
  for(auto i:v[s]) if(q[i]) tp_dfs(v,q,i,sorted);
  sorted.push(s);
}
void tpsort(vector<vector<ll>> &v,stack<ll> &sorted){
  ll n=v.size();
  vector<bool> q(n,1);
  for(ll i=0;i<n;i++){
    if(q[i]) tp_dfs(v,q,i,sorted);
  }
}

void scc_dfs(vector<vector<ll>> &v,vector<bool> &q,ll s,vector<vector<ll>> &list){
  q[s]=0;
  list[list.size()-1].push_back(s);
  for(auto i:v[s]){
    if(q[i]) scc_dfs(v,q,i,list);
  }
}
void scc(vector<vector<ll>> &v,vector<vector<ll>> &rv,vector<vector<ll>> &list){
  stack<ll> sorted;
  tpsort(v,sorted);
  ll n=v.size();
  vector<bool> q(n,1);
  while(!sorted.empty()){
    ll i=sorted.top();
    sorted.pop();
    if(q[i]){
      list.push_back(vector<ll>(0));
      scc_dfs(rv,q,i,list);
    }
  }
}

int main(){
  ll n,x,mans=0;
  cin>>n;
  auto v=vec<ll>({n,0},0);
  auto rv=vec<ll>({n,0},0);
  auto rv2=vec<ll>({n},0);
  for(ll i=0;i<n;i++){
    cin>>x;
    v[i].push_back(--x);
    rv[x].push_back(i);
  }
  
  queue<ll> q;
  for(ll i=0;i<n;i++){
    if(rv[i].size()==0) q.push(i);
    rv2[i]=rv[i].size();
  }
  while(!q.empty()){
    ll i=q.front();
    for(auto j:v[i]){
      rv2[j]--;
      if(rv2[j]==0) q.push(j);
    }
    q.pop();
    mans++;
  }

  auto list=vec<ll>({0,0},0);
  scc(v,rv,list);
  
  cout<<list.size()-mans<<"\n";
}
0