結果

問題 No.3650 Teleportation Cycles
コンテスト
ユーザー acphot2
提出日時 2026-09-07 19:55:18
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 191 ms / 2,000 ms
+ 909µs
コード長 1,328 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 83 ms
コンパイル使用メモリ 82,880 KB
実行使用メモリ 144,636 KB
最終ジャッジ日時 2026-09-07 19:55:44
合計ジャッジ時間 5,242 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n   # 最初は全員1人グループ

    def find(self, x):
        if self.parent[x] == x:
            return x

        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        # すでに同じグループ
        if root_x == root_y:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.size[root_y] += self.size[root_x]

        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]

        else:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]
            self.rank[root_x] += 1

    def group_size(self, x):
        root = self.find(x)
        return self.size[root]

def count_groups(uf):
    roots = set()
    for i in range(len(uf.parent)):
        roots.add(uf.find(i))
    return len(roots)

N = int(input())
A = list(map(int, input().split()))

uf = UnionFind(N)

for i in range(N):
    uf.union(i, A[i]-1)
    
group_count = count_groups(uf)

print(group_count)
0