题意

Link

Sol

给个其他题解都没给出过的方法:二分答案。

然后怎么 check 呢？

看 这个帖子。

（完）

解法：

抽象成图论问题：给定无向图，试给边加上方向使得每个点入度至少为 1。

二分答案，设二分到的答案是 $u$。

对于每一条边，若两个节点都大于 $u$，跳过之。

若两个节点仅一个大于 $u$，则指向小于 $u$ 的点，这个点成为 “自由点”。

然后连接所有剩下的边。

若最后存在没有自由点的树，那么不合法，否则合法。证明显然。

复杂度 $O(n\log m\alpha(n))$，其中 $m$ 是节点数，也就是最大的属性值。

Code

大概是因为我 sb 一样动态开并查集所以要开 O2，我也不知道为啥 O2 能从 1200ms+ 优化到 200ms。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
using namespace std;
const inline void readln(int&I){
	I=0;char C=getchar();
	while(!isdigit(C))C=getchar();
	while( isdigit(C))I=(I<<3)+(I<<1)+C-'0',C=getchar();
}
#define pii pair<int,int>
int n,c1,c2;
vector<pii >e;
bool operator<(pii pa,pii pb){
	if(pa.first==pb.first)return pa.second<pb.second;
	else return pa.first<pb.first;
}
int fi(vector<int>*f,int o){
	if((*f).at(o)==o)return o;
	else return (*f).at(o)=fi(f,(*f).at(o));
}
bool check(int u){
	vector<int>f(u+1),g(u+1);
	for(int i=1;i<=u;i++)
		f.at(i)=i,g.at(i)=0;
	for(int i=e.size()-1;i>=0;i--){
		if(e[i].first>u){
			if(e[i].second<=u)
				g.at(fi(&f,e[i].second))=1;
			continue;
		}
		int v1=fi(&f,e[i].first),v2=fi(&f,e[i].second);
		if(v1!=v2)f[v2]=v1,g[v1]|=g[v2];
		else g[v2]=1;
	}
	for(int i=1;i<=u;i++)
		if(f[i]==i && g[i]==0)return 0;
	return 1;
}
int main(){
	readln(n);
	for(int i=1;i<=n;i++)
		readln(c1),readln(c2),
		e.push_back(make_pair(max(c1,c2),min(c1,c2)));
	int l=0,r=n+1;
	while(l+1<r){//[l,r)
		int mid=((l+r)>>1);
		if(check(mid))l=mid;
		else r=mid;
	}
	printf("%d\n",l);
}