結果
問題 | No.1390 Get together |
ユーザー |
![]() |
提出日時 | 2021-02-13 16:43:13 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,810 ms / 2,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 2,755 ms |
コンパイル使用メモリ | 79,936 KB |
実行使用メモリ | 95,748 KB |
最終ジャッジ日時 | 2024-07-20 19:49:45 |
合計ジャッジ時間 | 32,299 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();HashMap<Integer, TreeSet<Integer>> counts = new HashMap<>();for (int i = 0; i < n; i++) {int b = sc.nextInt() - 1;int c = sc.nextInt();if (!counts.containsKey(c)) {counts.put(c, new TreeSet<>());}counts.get(c).add(b);}int ans = 0;UnionFindTree uft = new UnionFindTree(m);for (TreeSet<Integer> set : counts.values()) {int x = set.pollFirst();for (int y : set) {if (!uft.same(x, y)) {ans++;uft.unite(x, y);}}}System.out.println(ans);}static class UnionFindTree {int[] parents;public UnionFindTree(int x) {parents = new int[x];for (int i = 0; i < x; i++) {parents[i] = i;}}public int find(int x) {if (x == parents[x]) {return x;} else {return parents[x] = find(parents[x]);}}public boolean same(int x, int y) {return find(x) == find(y);}public void unite(int x, int y) {if (!same(x, y)) {parents[find(x)] = find(y);}}}}