Submission #74772359

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> r(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> r[i];
    }
    vector<vector<int>> adj(n + 1);
    for (int j = 0; j < m; ++j) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }

    vector<bool> available(n + 1, true);
    vector<int> partner(n + 1, 0);
    vector<int> order(n);
    for (int i = 0; i < n; ++i) order[i] = i + 1;
    sort(order.begin(), order.end(), [&](int a, int b) {
        return r[a] > r[b];
    });

    for (int x : order) {
        if (!available[x]) continue;
        for (int y : adj[x]) {
            if (available[y]) {
                partner[x] = y;
                partner[y] = x;
                available[x] = false;
                available[y] = false;
                break;
            }
        }
    }

    cout << partner[1] << endl;
    return 0;
}

Submission Info

Judge Result