[Codeforces] 1027F. Session in BSU

題目連結:https://codeforces.com/problemset/problem/1027/F

---

我好笨QAQ
本題關鍵大概是想到可以把每個考試當做邊來看吧OAO（看了解才知道
假設知道這件事後，那其實就很簡單，當然對於每個連通元件分開處理，明顯的如果邊數較點數多，那一定無法構造出一個合法的結果。
接著當邊數跟點數一樣多的時候，一定存在解，因為他必定可拆成幾個環跟一些連接的邊，那這時這裡的答案就是點的最大值。
還有邊數是點數減一的時候，不難發現他是顆樹，然後答案會是次大值。
邊數是點數減二的時候則不可能出現，所以討論這幾種狀況就可以得到答案了。

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
using PII = pair<int,int>;
#define PB push_back
#define FF first
#define SS second
#define ALL(x) begin(x), end(x)
#define SZ(x) (static_cast<int>(std::size(x)))
const int N = 2000000 + 5;

class LiSan{
	private:
		vector<lld> vv;
	public:
		template<typename... Args>
		void insert(lld x, Args& ...oth){insert(x);insert(oth...);}
		void insert(lld x){vv.PB(x);}
		void done(){
			sort(ALL(vv));
			vv.resize(distance(vv.begin(), unique(ALL(vv))));
		}
		int size() const { return SZ(vv); }
		int get(lld x){
			return static_cast<int>(distance(vv.begin(), lower_bound(ALL(vv), x)));
		}
		lld inv_get(int x){return vv[x];}
		void clear(){vv.clear();}
} lisan;

class DJS{
	private:
		vector<int> arr;
	public:
		void init(int n){
			arr.resize(n);
			iota(ALL(arr), 0);
		}
		int query(int x){
			if(arr[x] != x) arr[x] = query(arr[x]);
			return arr[x];
		}
		void merge(int x, int y){arr[query(x)]=query(y);}
} djs;

PII arr[N], mx[N];
int egs[N], vtx[N];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin >> n;
	for(int i=0;i<n;i++) cin >> arr[i].FF >> arr[i].SS;
	for(int i=0;i<n;i++) lisan.insert(arr[i].FF, arr[i].SS);
	lisan.done();
	for(int i=0;i<n;i++) arr[i].FF = lisan.get(arr[i].FF), arr[i].SS=lisan.get(arr[i].SS);
	djs.init(SZ(lisan));
	for(int i=0;i<n;i++) djs.merge(arr[i].FF, arr[i].SS);
	for(int i=0;i<n;i++) egs[djs.query(arr[i].FF)]++;
	for(int i=0;i<SZ(lisan);i++){
		int id = djs.query(i), val = lisan.inv_get(i);
		vtx[id]++;
		if(val >= mx[id].FF) mx[id].SS = mx[id].FF, mx[id].FF = val;
		else if(val > mx[id].SS) mx[id].SS = val;
	}
	int ans = -1;
	for(int i=0;i<SZ(lisan);i++){
		if(egs[i] > vtx[i]){
			ans = -1;
			break;
		}else if(egs[i] == vtx[i])
			ans = max(ans, mx[i].FF);
		else if(egs[i] == vtx[i]-1)
			ans = max(ans, mx[i].SS);
	}
	cout << ans << '\n';
	return 0;
}