Wormhole sort USACO

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
#define all(x) begin(x), end(x)
using pi = pair<int,int>;
#define F first
#define S second

void setIO(string name = "") { // name is nonempty for USACO file I/O

    ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output

    // alternatively, cin.tie(0)->sync_with_stdio(0);

    if (name.size()) {

        freopen((name+".in").c_str(), "r", stdin); // see Input & Output

        freopen((name+".out").c_str(), "w", stdout);

    }

}


const int mx = 1e5 + 7;

vector <int> adj[mx];

bool cmp(pair <pair <int, int>, int > a, pair <pair <int, int> , int> b){
    return a.second < b.second;
}



int main() {

    setIO("wormsort");

    int n, m;
    cin >> n >> m;
    map <int, bool> necessary; // change necessary
    vector <int> p(n+1);
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        if(p[i] != i){
            necessary[i] = 1;
        }
    }

    vector <pair < pair <int, int> , int> > edges;

    for(int i = 0; i < m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        edges.push_back({{u, v}, c});
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    sort(all(edges), cmp);

    bool ok = 0;
    int ans = edges[0].S;

    for(int i = 1; i <= n; i++){
        if(p[i] != i){
            ok = 1;
        }
    }
    if(!ok){
        cout << "-1" << endl;
        return 0;
    }


    for(auto x: edges){
        int u, v, c;
        u = x.F.F, v = x.F.S, c = x.S;

        /*3 cases: 1. both are unnecessary
        2. one necessary -> jeta necessary itar node size jodi 1 oy taile otau answer
        3. both necessary. -> jekunu tar node size jodi 1 oy taile otaw answer
        */
        if((!necessary[u] and necessary[v]) or (necessary[u] and !necessary[v])){
            if(necessary[u] and adj[u].size() <= 1){
                ok = 1;
                ans = c;
                break;
            }
            else if(necessary[v] and adj[v].size() <= 1){
                ok = 1;
                ans = c;
                break;
            }
        }
        else if((necessary[u] and necessary[v]) and (adj[u].size() <= 1 or adj[v].size() <= 1) ){
            ok = 1;
            ans = c;
            break;
        }
        else{
            // we need to delete the edge from the graph
            // delete v from adj[u]
            int posv = 0;
            for(auto x: adj[u]){
                if(x == v){
                    break;
                }
                posv++;
            }
            adj[u].erase(adj[u].begin()+posv);
            // delete u from adj[v]
            int posu = 0;
            for(auto x: adj[v]){
                if(x == u){
                    break;
                }
                posu++;
            }
            adj[v].erase(adj[v].begin()+posu);
        }
    }

    cout << ans << endl;

    return 0;
}