题目概述

有 $n$ 场考试，第 $i$ 场考试可以在 $a_i,b_i$ 两天中的一天完成，问至少什么时候能考完所有试，无解输出 $-1$ 。

解题报告

我图样图森破，以为是神仙贪心，结果是转化思维题。

把 $a_i,b_i$ 当做一条双向边，那么问题转化为每条边控制一个点，使得控制的点的点权最小。

然后就斯波了，可以每个连通块分类讨论：

1. 边数大于点数：无解，因为不可能每条边控制一个点。
2. 边数等于点数：每个点都会被控制，求点权最大值。
3. 边数小于点数：一棵树，可以避免最大值被选，求次大值。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000000,maxt=maxn<<1;

int n,x[maxn+5],y[maxn+5],a[maxt+5],ans;
int fa[maxt+5],si[maxt+5],num[maxt+5],MAX[maxt+5],lst[maxt+5];

inline int Find(int x,int L=1,int R=a[0]){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        a[mid]<=x?L=mid+1:R=mid-1;return R;
}
int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void Fix(int i,int x) {if (x>MAX[i]) lst[i]=MAX[i],MAX[i]=x; else if (x>lst[i]) lst[i]=x;}
inline void Merge(int x,int y){
    x=getfa(x);y=getfa(y);if (x==y) {num[x]++;return;}
    fa[x]=y,si[y]+=si[x];num[y]+=num[x]+1;Fix(y,MAX[x]);Fix(y,lst[x]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]),a[++a[0]]=x[i],a[++a[0]]=y[i];
    sort(a+1,a+1+a[0]);a[0]=unique(a+1,a+1+a[0])-a-1;for (int i=1;i<=a[0];i++) fa[i]=i,si[i]=1,MAX[i]=a[i];
    for (int i=1;i<=n;i++) Merge(Find(x[i]),Find(y[i]));
    for (int i=1;i<=a[0];i++)
        if (getfa(i)==i){
            if (num[i]>si[i]) return puts("-1"),0;
            num[i]<si[i]?ans=max(ans,lst[i]):ans=max(ans,MAX[i]);
        }
    return printf("%d\n",ans),0;
}