結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
![]() |
提出日時 | 2025-02-11 19:31:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 864 bytes |
コンパイル時間 | 503 ms |
コンパイル使用メモリ | 82,668 KB |
実行使用メモリ | 112,916 KB |
最終ジャッジ日時 | 2025-02-11 19:31:17 |
合計ジャッジ時間 | 8,615 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
def find(x): if P[x] == x: return x else: P[x] = find(P[x]) #経路圧縮 return P[x] # return find(P[x]) #経路圧縮なし def same(x,y): return find(x) == find(y) def merge(x,y): x = find(x) y = find(y) if x == y: return 0 if x > y: x,y = y,x P[y] = x N,M = map(int,input().split()) P = [i for i in range(N)] C = list(map(int,input().split())) G = [[] for _ in range(N)] for i,c in enumerate(C): c -= 1 G[c].append(i) for i in range(M): u,v = map(int,input().split()) u -= 1 v -= 1 if C[u] == C[v]: merge(u,v) ans = 0 for i in range(N): if G[i]: if len(G[i]) == 1: continue ng = len(G[i]) for j in range(1,ng): if not same(G[i][0],G[i][j]): merge(G[i][0],G[i][j]) ans += 1 print(ans)