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

https://yukicoder.me/problems/no/629

解法

https://yukicoder.me/submissions/228019

全ての頂点について、その頂点を門松列の中心とする門松パスが存在するかを確認していこう。
ある頂点cuと繋がっている全ての頂点toに対して、
up := A[cu] ＜ A[to]となっているA[to]
dn := A[cu] ＞ A[to]となっているA[to]
をカウントしていく。
もし、upかdnのサイズが2以上ならば門松パスが作れるので、答えをYESにする。
1つもそういう頂点が無ければNOを答える。
　
グラフの頂点は隣接行列ではなく隣接リストで保持するのがオススメ。
（隣接行列の方がいい場合もある。ワーシャルフロイドやるとか）

int N, M, A[1010];
vector<int> E[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    string ans = "NO";
    rep(cu, 0, N) {
        set<int> up, dn;
        fore(to, E[cu]) {
            if (A[cu] < A[to]) up.insert(A[to]);
            if (A[cu] > A[to]) dn.insert(A[to]);
        }

        if (2 <= up.size()) ans = "YES";
        if (2 <= dn.size()) ans = "YES";
    }
    cout << ans << endl;
}