提出 #49107882

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define sz(c) int((c).size())
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define per(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); --i)
using ll = long long;

template <typename DiGraph>
DiGraph Transpose(int n, const DiGraph &adj) {
    DiGraph rev_adj(n);
    for (int v = 0; v < n; ++v)
        for (int u : adj[v])
            rev_adj[u].push_back(v);
    return rev_adj;
}

template <typename DiGraph>
std::vector<int> TopSort(int n, const DiGraph &adj) {
    std::vector<int> order;
    std::vector<bool> visited(n);
    auto DFS = [&](auto &&self, int v) -> void {
        visited[v] = true;
        for (int u : adj[v])
            if (!visited[u])
                self(self, u);
        order.push_back(v);
    };
    for (int v = 0; v < n; ++v)
        if (!visited[v])
            DFS(DFS, v);
    std::reverse(order.begin(), order.end());
    return order;
}

template <typename DAG>
struct Condensation {
    int components_count;
    std::vector<int> component;
    DAG adj;
};

template <typename DiGraph, typename DAG = DiGraph>
Condensation<DAG> BuildCondensation(int n, const DiGraph &adj) {
    Condensation<DAG> result;
    result.components_count = 0;
    result.component.resize(n);
    auto rev_adj = Transpose(n, adj);
    std::vector<bool> visited(n);

    auto DFS = [&](auto &&self, int v) -> void {
        visited[v] = true;
        result.component[v] = result.components_count;
        for (int u : rev_adj[v])
            if (!visited[u])
                self(self, u);
    };

    for (int v : TopSort(n, adj))
        if (!visited[v]) {
            DFS(DFS, v);
            ++result.components_count;
        }

    result.adj.resize(result.components_count);
    for (int v = 0; v < n; ++v) {
        int vc = result.component[v];
        for (int u : adj[v]) {
            int uc = result.component[u];
            if (vc != uc)
                result.adj[vc].push_back(uc);
        }
    }

    for (auto &vec : result.adj) {
        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }

    return result;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(N);
    for (auto &a : A)
        std::cin >> a;

    std::vector<std::vector<int>> adj(N);
    rep(i, 0, M) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        if (A[u] <= A[v])
            adj[u].push_back(v);
        if (A[v] <= A[u])
            adj[v].push_back(u);
    }

    auto condensation = BuildCondensation(N, adj);

    const auto &component = condensation.component;
    int cc = condensation.components_count;
    std::vector<int> dp(cc);
    dp[component[0]] = 1;
    rep(v, 0, cc) if (dp[v] != 0) {
        for (int u : condensation.adj[v])
            dp[u] = std::max(dp[u], dp[v] + 1);
    }
    std::cout << dp[component[N - 1]] << "\n";
}

提出情報

ジャッジ結果