結果
問題 |
No.1390 Get together
|
ユーザー |
|
提出日時 | 2022-12-11 20:34:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 404 ms / 2,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,280 KB |
実行使用メモリ | 103,972 KB |
最終ジャッジ日時 | 2024-10-15 16:17:32 |
合計ジャッジ時間 | 8,186 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
class UnionFind(): def __init__(self,n): self.par = [-1] * n self.rank = [0] * n self.siz = [1] * n def root(self,x): if self.par[x] == -1: return x else: self.par[x] = self.root(self.par[x]) return self.par[x] def issame(self,x,y): return self.root(x) == self.root(y) def unite(self,x,y): rx = self.root(x) ry = self.root(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: rx,ry = ry,rx self.par[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 self.siz[rx] += self.siz[ry] return True def size(self,x): return self.siz[self.root(x)] N,M = map(int,input().split()) uf = UnionFind(N+1) L = [[] for i in range(N+1)] for i in range(N): b,c = map(int, input().split()) L[c].append(b) uf = UnionFind(M+1) cnt = 0 for l in L: for c in l: if not uf.issame(l[0],c): uf.unite(l[0],c) cnt+=1 print(cnt)