Submission #74771986

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n,m;
    cin>>n>>m;
    vector<ll>r(n+1);
    for(int i= 1; i<=n; i++)cin>>r[i];

    vector<vector<ll>>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<ll>order(n);
    iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(), [&](int a, int b){
        return r[a] > r[b];
    });

    vector<ll>partner(n+ 1, 0);
    for(int x : order){
        if (partner[x] != 0)continue; 
        for(int y : adj[x]){
            if(partner[y] == 0){
                partner[x] = y;
                partner[y] = x;
                break;
            }
        }
    }
    cout<<partner[1]<<endl;
    return 0;
}

Submission Info

Judge Result