E

 avatar
meda
c_cpp
a month ago
2.0 kB
14
Indexable
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
template<class T>
void printff(vector<T>& v) {
  for (auto k : v) cout << k << " ";
  cout << endl;
}
const int N = 1e7 + 5;
bool exist[N];
int prevsum[N], pos[N];
struct DSU{
    int n;
    vector<int> parent, size;
    int components;
    DSU(int n){
        parent = size = vector<int>(n + 1);
        components = n;
        for (int i = 1; i <= n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }
    int find(int v){
        return parent[v] = (parent[v] == v ? v : find(parent[v]));
    }
    void union_sets(int a, int b){
        a = find(a);
        b = find(b);
        if (a != b){
            if (size[a] < size[b]) swap(a, b);
            parent[b] = a;
            size[a] += size[b];
            components--;
        }
    }
};

void SOLVE() {
    int n, m; cin >> n >> m;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        exist[a[i]] = true;
        pos[a[i]] = i;
    }
    
    for(int i = 1; i < N; i++) prevsum[i] = prevsum[i - 1] + exist[i];

    int l = 1, r = N;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(prevsum[mid] == mid) l = mid;
        else r = mid;
    }
    
    vector<vector<int>> graph(n + 1);
    for(int i = 0, u, v; i < m; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    DSU tree(l);
    int mx = 1;
    for(int i = 2; i <= l; i++){
        for(auto child : graph[pos[i]]){
            if(a[child] < i){
                tree.union_sets(i, a[child]);
            }
        }
        if(tree.components == l - i + 1) mx = max(mx, i);
    }
    
    cout << mx << endl;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);
  int tc = 1; // cin >> tc;
  while(tc--) SOLVE();
  return 0;
}
Leave a Comment