結果

問題 No.2563 色ごとのグループ
ユーザー flippergo
提出日時 2025-07-22 14:56:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 925 ms / 2,000 ms
コード長 699 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 141,000 KB
最終ジャッジ日時 2025-07-22 14:56:19
合計ジャッジ時間 12,002 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())
C = [0]+list(map(int,input().split()))
T = [[i,0] for i in range(N+1)]
def find(x):
    if T[x][0]==x:return x
    return find(T[x][0])
def union(x,y):
    rx = find(x)
    ry = find(y)
    if rx==ry:return
    if T[ry][1]<T[rx][1]:
        T[ry][0] = rx
    elif T[ry][1]>T[rx][1]:
        T[rx][0] = ry
    else:
        T[ry][0] = rx
        T[rx][1] += 1
D = {}
for _ in range(M):
    a,b = map(int,input().split())
    if C[a]==C[b]:
        union(a,b)
D = {}
for i in range(1,N+1):
    rt = find(i)
    if C[rt] not in D:
        D[C[rt]] = set()
    D[C[rt]].add(rt)
ans = 0
for c in D:
    ans += len(D[c])-1
print(ans)
0