考え方
$x$から$A_{x}$に辺を張った有向グラフを考える．グラフの閉路に含まれる頂点であることが，高橋君の勝つ必要十分条件．
この頂点の個数をカウントすれば良い．
アライグマ「E問題は、iからAiに有向辺を張ったグラフを考えると「どんなKが選ばれても、スタート地点をうまく選べば、K回移動したあと頂点iにいられる」ようなiの個数を考えればいいのだ。サイクルの中の頂点があればいいから、そういう頂点の個数を頑張って求めるのだ！」 pic.twitter.com/VodhgVnLtL
— 競技プログラミングをするフレンズ (@kyopro_friends) April 1, 2023
回答例 (Functional Graphであることを利用)
各頂点から1つの有向辺が出ているグラフをFunctional Graphという．（すべての頂点の出次数が 1 の有向グラフ）
Functional Graphの各連結成分には閉路が一つだけ存在する．
参考：Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)
ループ外からループに入ってくる辺を全て消したグラフを考える（ループに関係する頂点・辺だけを残して，他を全て消したグラフ）．
このグラフの頂点の入次数の合計が，ループの頂点の個数（答え）と一致する．
そこで，次を可能な限り繰り返して，入次数の和をとったものが答えになる．
- 入次数 (indegree)がゼロの頂点から出ている辺の終点の入次数を-1する．
うまいなぁ．．．
回答例 (UnionFind)
- UnionFindで閉路を検出 & 連結成分を求める（閉路検出 - 競プロはじめました）．
- 閉路となる連結成分に含まれる頂点の数をBFSで数える．
from collections import deque N = int(input()) A = list(map(int, input().split())) # --- UnionFind --- p = [-1] * (N + 1) def root(x): if p[x] < 0: return x p[x] = root(p[x]) return p[x] def unite(x, y): x = root(x) y = root(y) if x == y: return p[x] += p[y] p[y] = x def size(x): x = root(x) return -p[x] # --- UnionFind --- G = [[] for _ in range(N)] loop = set() for i, a in enumerate(A): a -= 1 G[i].append(a) if root(i) == root(a): loop.add(i) loop.add(a) else: unite(i, a) ans = 0 seen = [False] * N for i in range(N): if seen[A[i] - 1]:continue if A[i] - 1 in loop: q = deque([A[i] - 1]) while q: cur = q.popleft() ans += 1 seen[cur] = True for chi in G[cur]: if not seen[chi]: q.append(chi) print(ans)
