結果

問題 No.3650 Teleportation Cycles
コンテスト
ユーザー moon17
提出日時 2026-08-28 23:11:39
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,107 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 274 ms
コンパイル使用メモリ 96,108 KB
実行使用メモリ 162,056 KB
最終ジャッジ日時 2026-08-28 23:11:46
合計ジャッジ時間 6,089 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://github.com/shakayami/ACL-for-python/blob/master/scc.py
def scc(N, edges):
    M = len(edges)
    start = [0] * (N + 1)
    elist = [0] * M
    for e in edges:
        start[e[0] + 1] += 1
    for i in range(1, N + 1):
        start[i] += start[i - 1]
    counter = start[:]
    for e in edges:
        elist[counter[e[0]]] = e[1]
        counter[e[0]] += 1

    low = [0] * N
    Ord = [-1] * N
    ids = [0] * N
    visited = []
    now_ord = 0
    group_num = 0

    for root in range(N):
        if Ord[root] != -1:
            continue
        node_stack = [root]
        it_stack = [start[root + 1] - 1]
        low[root] = Ord[root] = now_ord
        now_ord += 1
        visited.append(root)
        while node_stack:
            v = node_stack[-1]
            i = it_stack[-1]
            if i >= start[v]:
                it_stack[-1] = i - 1
                to = elist[i]
                if Ord[to] == -1:
                    low[to] = Ord[to] = now_ord
                    now_ord += 1
                    visited.append(to)
                    node_stack.append(to)
                    it_stack.append(start[to + 1] - 1)
                elif Ord[to] < low[v]:
                    low[v] = Ord[to]
            else:
                node_stack.pop()
                it_stack.pop()
                if low[v] == Ord[v]:
                    while True:
                        u = visited.pop()
                        Ord[u] = N
                        ids[u] = group_num
                        if u == v:
                            break
                    group_num += 1
                if node_stack:
                    bef = node_stack[-1]
                    if low[v] < low[bef]:
                        low[bef] = low[v]

    for i in range(N):
        ids[i] = group_num - 1 - ids[i]
    groups = [[] for _ in range(group_num)]
    for i in range(N):
        groups[ids[i]].append(i)
    return groups
n,*a=map(int,open(0).read().split())
edges=[]
for i in range(n):
  edges+=(i,a[i]-1),
t=[-1]*n
ans=0
for sc in scc(n,edges):
  if len(sc)>1 or i==a[i]-1:
    ans+=1
print(ans)
0