[yukicoder] No.629 グラフの中に眠る門松列

問題

隣接するノードの値に門松列が含まれるかどうかを調べる問題です。

No.629 グラフの中に眠る門松列 - yukicoder

考え方

門松列はノードが三つあれば判定ができるので、隣接リストを考えると分かりやすいと思います。

隣接リストはあるノードに隣接するノードを列挙したものです。どう表現するかですか、MapとArrayListを用いて、キーに注目するノードを設定し、値にそのノードに隣接するノードのリストを入れていけば良いです。

隣接リストを作成する上では、ノードの値である は無視して大丈夫です。

注目するノードを固定し、その隣接リストに含まれるノードの値が注目するノードの値より大きいものと小さいものの個数を重複を許さずにカウントします。

カウントしたものが2以上となれば門松列が存在することになります。

コード

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Exec0629 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[]a = new int[N];
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }
        int[]u = new int[M];
        int[]v = new int[M];
        for(int i = 0; i < M; i++) {
            u[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        scan.close();
        // 隣接リスト
        Map<Integer, ArrayList<Integer>> G
        = new HashMap<Integer, ArrayList<Integer>>();
        for(int i = 0; i < M; i++) {
            if(G.containsKey(u[i])) {
                G.get(u[i]).add(v[i]);
            }else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(v[i]);
                G.put(u[i], list);
            }
            if(G.containsKey(v[i])) {
                G.get(v[i]).add(u[i]);
            }else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(u[i]);
                G.put(v[i], list);
            }
        }
        // あるノードに注目したとき、門松列を作れるかどうかを調べる。
        for(int k : G.keySet()) {
            ArrayList<Integer> list = G.get(k);
            if(list.size() >= 2) {
                int t1 = a[k - 1];
                Set<Integer> up = new HashSet<Integer>();
                Set<Integer> dw = new HashSet<Integer>();
                for(int i = 0; i < list.size(); i++) {
                    if(t1 > a[list.get(i) - 1]) {
                        up.add(a[list.get(i) - 1]);
                    }else if(t1 < a[list.get(i) - 1]) {
                        dw.add(a[list.get(i) - 1]);
                    }
                }
                if(up.size() >= 2 || dw.size() >= 2) {
                    System.out.println("YES");
                    System.exit(0);
                }
            }
        }
        System.out.println("NO");
    }
}