新・アルゴリズムとデータ構造入門 Java編13:ヒープの判定

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

    }
}

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

    }
}

import java.util.*;

public class Main {
    static Map<Integer, Integer> weightAndId = new HashMap<>();
    static Map<Integer, Integer> idAndWeight = new HashMap<>();

    static int getIdFromWeight(int weight) {
        if (!weightAndId.containsKey(weight)) {
            weightAndId.put(weight, weightAndId.size());
        }
        int id = weightAndId.get(weight);
        idAndWeight.put(id, weight);
        return id;
    }

    static int getWeight(int id) {
        return idAndWeight.get(id);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int[] tree = new int[N];

        for (int i = 0; i < N; i++) {
            tree[i] = i;
        }

        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();

            int aid = getIdFromWeight(aw);
            int bid = getIdFromWeight(bw);

            tree[bid] = aid;
        }

        boolean isMaxHeap = true;
        for (int i = 0; i < N; i++) {
            int childId = /* */;
            int parentId = /* */;

            if (childId == parentId) {
                continue;
            }

            if (/* */) {
                isMaxHeap = false;
            }
        }

        if (isMaxHeap) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

import java.util.*;

public class Main {
    static Map<Integer, Integer> weightAndId = new HashMap<>();
    static Map<Integer, Integer> idAndWeight = new HashMap<>();

    static int getIdFromWeight(int weight) {
        if (!weightAndId.containsKey(weight)) {
            weightAndId.put(weight, weightAndId.size());
        }
        int id = weightAndId.get(weight);
        idAndWeight.put(id, weight);
        return id;
    }

    static int getWeight(int id) {
        return idAndWeight.get(id);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int[] tree = new int[N];

        for (int i = 0; i < N; i++) {
            tree[i] = i;
        }

        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();

            int aid = getIdFromWeight(aw);
            int bid = getIdFromWeight(bw);

            tree[bid] = aid;
        }

        boolean isMaxHeap = true;
        for (int i = 0; i < N; i++) {
            int childId = /* */;
            int parentId = /* */;

            if (childId == parentId) {
                continue;
            }

            if (/* */) {
                isMaxHeap = false;
            }
        }

        if (isMaxHeap) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「最大ヒープの判定」

根つき木について、頂点の数 N と根に紐づく値 R、N-1 個の辺について両端の頂点に紐づく値の組(親: a_i, 子: b_i)が与えられるので、この根つき木が最大ヒープであるか判定して結果を出力してください。
コードエリアには、入力値を受け取るコードと、判定結果を出力するコードが実装されているので、コードを書き足して完成させてください。

制約

・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ R ≦ N
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
・与えられる根つき木の中に同じ値は 2 つ以上含まれない

入力される値

5 10
10 11
10 9
9 3
3 2

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃06:ヒープの判定

このチャプターでは、ヒープの判定について学習します。
レベルアップ問題集「木のメニュー」に収録されている「ヒープの判定」の問題を解きます。

出力例1

NO

入力例2

10 91753
91753 76540
76540 31536
31536 14625
31536 22346
91753 36347
22346 5911
91753 26082
76540 70927
36347 32065

出力例2

YES

完成コード

import java.util.*;

public class Main {
    static Map<Integer, Integer> weightAndId = new HashMap<>();
    static Map<Integer, Integer> idAndWeight = new HashMap<>();

    // 頂点のweightに対応する頂点のidを取得する
    static int getIdFromWeight(int weight) {
        if (!weightAndId.containsKey(weight)) { // 新しいweightならば、新しいidを割り振る
            weightAndId.put(weight, weightAndId.size());
        }
        int id = weightAndId.get(weight);
        idAndWeight.put(id, weight);
        return id;
    }

    // 頂点のidに対応するweightを取得する
    static int getWeight(int id) {
        return idAndWeight.get(id);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 頂点の数
        int R = sc.nextInt(); // 根の頂点のweight
        int[] tree = new int[N]; // 根付き木に対応する配列

        // 各頂点の親を自身として初期化
        for (int i = 0; i < N; i++) {
            tree[i] = i;
        }

        // 辺の数だけループして入力
        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();

            int aid = getIdFromWeight(aw);
            int bid = getIdFromWeight(bw);

            // 頂点bの親を頂点aとする
            tree[bid] = aid;
        }

        // 最大ヒープの判定
        boolean isMaxHeap = true;
        for (int i = 0; i < N; i++) {
            int childId = i;
            int parentId = tree[i];

            // 根ならば何もしない
            if (childId == parentId) {
                continue;
            }

            // (親の頂点のweight) >= (子の頂点のweight)ならば最大ヒープ
            if (getWeight(parentId) < getWeight(childId)) {
                isMaxHeap = false;
            }
        }

        if (isMaxHeap) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}