\(1\) 以上 \(N\) 以下の整数からなる集合を \(S\) (問題文中に登場する \(S\) と定義が異なるため注意) とし、 \(S\) から \(S\) への写像 \(f\) を \(f(x)=A_x\) で定めます。

さらに集合の列 \(S_0,S_1,\ldots\) を、\(S_0=S\)および、 \(1\leq i\)について \(S_i=f(S_{i-1})\) (すなわち、\(S_i=\{f(x)|x\in S_{i-1} \}\)) で定めます。 このとき、元の問題で高橋君が \(x\) 回目のゲームに勝つ必要十分条件は 任意の正整数 \(k\) について、 \(x\in S_k\) である事と言い換える事ができます。

さて、この集合の列 \(S_0,S_1,\ldots\) について、 \(S_0\supseteq S_1\) であり、定義から \(S_{i-1}\supseteq S_i\) ならば \(S_i\supseteq S_{i+1}\) が成り立つため、 帰納的に \(S_0\supseteq S_1\supseteq S_2\cdots\) が成り立ちます。
\(|S_0|=N\) であるから \(S_i\) は有限集合であり、 \(S_i\supsetneq S_{i+1}\) のとき \(|S_i|-1\geq |S_{i+1}|\) となる事に注意すると、 定義から 任意の \(i\) について \(|S_i|>0\) であることから、 ある \(0\leq i_0\leq N-1\) が存在して \(S_{i_0}=S_{i_0+1}\) となります。
このとき、\(S_i\) の定義から \(S_{i}=S_{i+1}\) ならば \(S_{i+1}=S_{i+2}\) であるから帰納的に \(S_{i_0}=S_{i_0+1}=S_{i_0+2}=\cdots\) となります。
ゆえに、このような \(i_0\) と \(S_{i_0}\) を求める事ができれば、\(S_{i_0}\) のサイズが答えとなります。

これを求める方法はいくつかありますが、例えば、 各 \(0\leq i\), \(1\leq y\leq N\) について、 \(S_i\) の要素 \(x\) のうち \(f(x)=y\) となるものの個数 \(c_{i,y}\) を管理すれば良いです。
\(c_{0,y}\) は \(A_x=y\) であるような \(y\) の個数なので簡単に求める事ができます。
ここで、ある \(y\) が \(S_1\) に含まれる必要十分条件は定義より \(c_{0,y}>0\) です。
次に、\(c_{1,y}\) を求める事を考えますが、これは \(c_{0,y}\) と \(c_{1,y}\) の差分を考えると、 \(x\in(S_0\backslash S_1)\) であるような \(x\) であって、\(f(x)=y\) であるようなものの個数を \(d_{1,y}\) として、 \(c_{1,y}=c_{0,y}-d_{1,y}\) となります。
\(y\) が \(S_2\) に含まれる必要十分条件は \(c_{1,y}>0\) であり、以下同様にして繰り返せば良いです。

これを愚直に行うと \(\Theta(N^2)\) の時間計算量がかかりますが、 \(c_{i,y}\) の配列を使い回し、\(d_{i,y}\) を求めて引く代わりに \(x\in(S_i\backslash S_{i+1})\) について \(c_{i,f(x)}\) の値をデクリメントする事でも同様の更新ができます。 また、\((S_i\backslash S_{i+1})\) の要素の候補としてあり得るのは上記のステップでデクリメントが行われたもののみであることに注意すると、いずれも全体で高々 \(N\) 回しか行われません。よって \(O(N)\) で計算する事ができ、十分高速にこの問題を解くことができました。

なお、実際は \(i\) について区別する事なく、最初に\(c_y\) が \(0\) であるものをqueue に加え、queue の要素 \(x\) に対して \(c_{f(x)}\) をデクリメントし、\(c_{f(x)}=0\) となったものをqueue に加える事を繰り返すことで答えを求めることができます。これは、頂点 \(i\) から 頂点 \(A_i\) に対して 辺を張った\(N\) 頂点 \(N\) 辺の有向グラフ上でこの問題を考えると分かりやすいです。

C++ による実装例 :

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void){
	int n,sz;
	cin>>n;
	vector<int>a(n),c(n);
	vector<vector<int> >b(n);
	int ans=n;
	rep(i,n){
		cin>>a[i];
		a[i]--,c[a[i]]++;
	}
	rep(i,n)if(c[i]==0){
		ans--;
		b[0].push_back(i);
	}
	rep(i,n-1){
		sz=b[i].size();
		if(sz==0)break;
		rep(j,sz){
			c[a[b[i][j]]]--;
			if(c[a[b[i][j]]]==0)ans--,b[i+1].push_back(a[b[i][j]]);
		}
	}
    cout<<ans<<endl;
	return 0;
}