結果

問題 No.3650 Teleportation Cycles
コンテスト
ユーザー 👑 loop0919
提出日時 2026-08-28 22:31:16
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 201 ms / 2,000 ms
+ 48µs
コード長 2,155 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 289 ms
コンパイル使用メモリ 96,104 KB
実行使用メモリ 170,452 KB
最終ジャッジ日時 2026-08-28 22:31:24
合計ジャッジ時間 6,316 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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 = int(input())
A = [int(s) - 1 for s in input().split()]

graph = [[] for _ in range(N)]
edges = []

for i, a in enumerate(A):
    edges.append((i, a))

ans = 0

for group in scc(N, edges):
    if len(group) == 1 and A[group[0]] != group[0]:
        continue
    ans += 1

print(ans)
0