結果
問題 | 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] * nself.rank = [0] * nself.siz = [1] * ndef root(self,x):if self.par[x] == -1:return xelse: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 Falseif self.rank[rx] < self.rank[ry]:rx,ry = ry,rxself.par[ry] = rxif self.rank[rx] == self.rank[ry]:self.rank[rx] += 1self.siz[rx] += self.siz[ry]return Truedef 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 = 0for l in L:for c in l:if not uf.issame(l[0],c):uf.unite(l[0],c)cnt+=1print(cnt)