Code : Non-Decreasing Colorful Path

#include <atcoder/dsu>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const int max_val = 2 * (int)1e5 + 1;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<vector<int>> vertices_with_value(max_val);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vertices_with_value[a[i]].push_back(i);
    }

    vector<vector<int>> adj(n);
    dsu d(n);
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (a[x] == a[y]) {
            d.merge(x, y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        } else if (a[x] < a[y]) {
            adj[x].push_back(y);
        } else {
            adj[y].push_back(x);
        }
    }

    for (int i = 0; i < n; i++) {
        int leader = d.leader(i);
        if (leader == i) {
            continue;
        }
        for (auto child : adj[i]) {
            adj[leader].push_back(child);
        }
        adj[i].clear();
    }

    // dp[i] is not set when i is not a leader of its component.
    // If i is the leader, dp[i] is the best path that starts from this
    // component and ends at n.
    vector<int> dp(n, 0);
    dp[d.leader(n - 1)] = 1;
    for (int val = max_val - 1; val >= 0; val--) {
        for (auto node : vertices_with_value[val]) {
            if (node != d.leader(node)) {
                continue;
            }
            for (auto child : adj[node]) {
                child = d.leader(child);
                if (child != node && dp[child] != 0) {
                    dp[node] = max(dp[node], 1 + dp[child]);
                }
            }
        }
    }

    cout << dp[d.leader(0)] << endl;
}

int main() {
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int max_val = 2 * (int)1e5 + 1;

class UnionFind {
  private:
    int n;
    // Parent array is intentionally kept private.
    // Use find_set instead.
    vector<int> parent;

  public:
    UnionFind(int n) {
        this->n = n;
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    int find_set(int u) {
        if (parent[u] == u) {
            return u;
        }

        int root_x = find_set(parent[u]);
        parent[u] = root_x;
        return root_x;
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);

        if (a != b) {
            parent[a] = b;
        }
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<vector<int>> vertices_with_value(max_val);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vertices_with_value[a[i]].push_back(i);
    }

    vector<vector<int>> adj(n);
    UnionFind dsu(n);
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (a[x] == a[y]) {
            dsu.union_sets(x, y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        } else if (a[x] < a[y]) {
            adj[x].push_back(y);
        } else {
            adj[y].push_back(x);
        }
    }

    for (int i = 0; i < n; i++) {
        int leader = dsu.find_set(i);
        if (leader == i) {
            continue;
        }
        for (auto child : adj[i]) {
            adj[leader].push_back(child);
        }
        adj[i].clear();
    }

    // dp[i] is not set when i is not a leader of its component.
    // If i is the leader, dp[i] is the best path that starts from this
    // component and ends at n.
    vector<int> dp(n, 0);
    dp[dsu.find_set(n - 1)] = 1;
    for (int val = max_val - 1; val >= 0; val--) {
        for (auto node : vertices_with_value[val]) {
            if (node != dsu.find_set(node)) {
                continue;
            }
            for (auto child : adj[node]) {
                child = dsu.find_set(child);
                if (child != node && dp[child] != 0) {
                    dp[node] = max(dp[node], 1 + dp[child]);
                }
            }
        }
    }

    cout << dp[dsu.find_set(0)] << endl;
}

int main() {
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int max_val = 2 * (int)1e5 + 1;

class UnionFind {
  public:
    int n;
    vector<int> parent;
    UnionFind(int n) {
        this->n = n;
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

  public:
    int find_set(int u) {
        if (parent[u] == u) {
            return u;
        }

        int root_x = find_set(parent[u]);
        parent[u] = root_x;
        return root_x;
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);

        if (a != b) {
            parent[a] = b;
        }
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<vector<int>> vertices_with_value(max_val);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vertices_with_value[a[i]].push_back(i);
    }

    vector<vector<int>> adj(n);
    UnionFind dsu(n);
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (a[x] == a[y]) {
            dsu.union_sets(x, y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        } else if (a[x] < a[y]) {
            adj[x].push_back(y);
        } else {
            adj[y].push_back(x);
        }
    }

    for (int i = 0; i < n; i++) {
        if (dsu.parent[i] == i) {
            continue;
        }
        int leader = dsu.find_set(i);
        for (auto child : adj[i]) {
            adj[leader].push_back(child);
        }
        adj[i].clear();
    }

    vector<int> dp(n, 0);
    dp[dsu.find_set(n - 1)] = 1;
    for (int val = max_val - 1; val >= 0; val--) {
        for (auto node : vertices_with_value[val]) {
            if (dsu.find_set(node) != node) {
                continue;
            }
            for (auto child : adj[node]) {
                if (dsu.find_set(child) != dsu.find_set(node) &&
                    dp[dsu.find_set(child)] != 0) {
                    dp[node] = max(dp[node], 1 + dp[dsu.find_set(child)]);
                }
            }
        }
    }

    cout << dp[dsu.find_set(0)] << endl;
}

int main() {
    solve();
    return 0;
}