题意

有 \(n\) 门课程，每门课程可以选择在 \(a_i\) 或者 \(b_i\) 天参加考试，每天最多考一门，问最早什么时候考完所有课程。

\(n\leq 10^6\)。

分析

• 类似 [BZOJ4883]棋盘上的守卫 一题。

• 将每门课程对应的两天连边，如果课程 \(i\) 要在第 \(x\) 天考，则对应边指向 \(x\) 。

• 最后有 \(n\) 天，\(n\) 条有向边，每条边的入度为1，构成了基环树森林。

• 总时间复杂度为 \(O(nlogn)\) (离散化)。

总结：这种 \(A\) 可以选择两种物品之一，每种物品最多被一个人选择的问题可以考虑基环树。

代码

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;i++)

typedef long double ld;

inline int gi(){

  int x=0,f=1;char ch=getchar();

  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}

  while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}

  return x*f;

}

template<typename T> inline bool Max(T& a, const T& b) {

    return a < b ? a = b, true : false;

}

template<typename T> inline bool Min(T& a, const T& b) {

    return a > b ? a = b, true : false;

}

const int N=1e6 + 7;

int n,len,ans;

int V[N<<1],par[N<<1],cir[N<<1],mx[N<<1],a[N],b[N];

int getpar(int a){return par[a]==a?a:par[a]=getpar(par[a]);}

int main(){

  n=gi();

  rep(i,1,n+n) par[i]=i;

  rep(i,1,n) V[++len]=a[i]=gi(),V[++len]=b[i]=gi();

  sort(V+1,V+1+len);

  len=unique(V+1,V+1+len)-V-1;

  rep(i,1,n){

    a[i]=lower_bound(V+1,V+1+len,a[i])-V;

	b[i]=lower_bound(V+1,V+1+len,b[i])-V;

	int f1=getpar(a[i]),f2=getpar(b[i]);

	if(cir[f1]&&cir[f2]) return puts("-1"),0;

	if(f1>f2) swap(f1,f2);Max(ans,V[f1]);

	if(f1==f2) {cir[f2]=1;continue;}

	par[f1]=f2,cir[f2]|=cir[f1];

  }

  printf("%d\n",ans);

  return 0;

}