E
#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