結果

問題 No.1390 Get together
ユーザー ks2m
提出日時 2021-02-12 21:55:16
言語 Java
(openjdk 23)
結果
AC  
実行時間 874 ms / 2,000 ms
コード長 1,816 bytes
コンパイル時間 2,138 ms
コンパイル使用メモリ 79,036 KB
実行使用メモリ 74,732 KB
最終ジャッジ日時 2024-07-19 21:13:03
合計ジャッジ時間 16,728 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            int b = Integer.parseInt(sa[0]) - 1;
            int c = Integer.parseInt(sa[1]) - 1;
            List<Integer> list = map.get(c);
            if (list == null) {
                list = new ArrayList<>();
                map.put(c, list);
            }
            list.add(b);
        }
        br.close();
        UnionFind uf = new UnionFind(m);
        for (Integer key : map.keySet()) {
            List<Integer> list = map.get(key);
            if (list.size() > 1) {
                int f = list.get(0);
                for (int i = 1; i < list.size(); i++) {
                    uf.union(f, list.get(i));
                }
            }
        }
        System.out.println(m - uf.num);
    }
    static class UnionFind {
        int[] parent, size;
        int num = 0; // 連結成分の数
        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            num = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
                num--;
            }
        }
        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }
        /**
         * xとyが同一連結成分か
         */
        boolean same(int x, int y) {
            return find(x) == find(y);
        }
        /**
         * xを含む連結成分のサイズ
         */
        int size(int x) {
            return size[find(x)];
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0