結果
問題 |
No.3024 全単射的
|
ユーザー |
|
提出日時 | 2025-02-15 09:55:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 338 ms / 5,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 82,840 KB |
実行使用メモリ | 156,388 KB |
最終ジャッジ日時 | 2025-02-15 09:55:44 |
合計ジャッジ時間 | 5,299 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
class UnionFind: def __init__(self, n): self.parent = [-1]*n def find(self, x): if self.parent[x] < 0: return x self.parent[x] = self.find(self.parent[x]) return self.parent[x] def merge(self, u, v): pu, pv = self.find(u), self.find(v) if pu==pv: return if self.parent[pu] > self.parent[pv]: pu, pv = pv, pu self.parent[pu] += self.parent[pv] self.parent[pv] = pu def leader(self, x): return self.find(x) def size(self, x): return -self.parent[self.find(x)] def main(): n, m = map(int, input().split()) vec = [] query = [] for _ in range(n): u, v = map(int, input().split()) vec.append(u) vec.append(v) query.append([u, v]) vec = sorted(list(set(vec))) dic = dict() for i, v in enumerate(vec): dic[v] = i for i in range(n): u, v = query[i] query[i] = dic[u], dic[v] uf = UnionFind(len(vec)) add = [] num = [0]*len(vec) for u, v in query: uf.merge(u, v) add.append(u) for v in add: num[uf.leader(v)] += 1 s = set() for i in range(len(vec)): s.add(uf.leader(i)) ans = 0 for v in s: ans += min(num[v], uf.size(v)) print(ans) if __name__ == "__main__": main()