F. Session in BSU
https://codeforces.com/contest/1027/problem/F
题意:
n场考试,每场可以安排在第ai天或者第bi天,问n场考完最少需要多少天。
分析:
将所有的a与b连边,一条边相当于一场考试,一个点相当于一个考试时间,每条边需要找一个点。
那么在一个联通块中,边数>点数,无解(这些考试都只能在这个联通块内的点考)。
如果边数=点数,那么相当于出现了环,每条边和一个点匹配,即n场考试,n个考试时间,所以这个联通块内的答案就是最大的点。
如果边数<点数,那么一定是一棵树,那么所有的最大的时间点就可以不选了,这个联通块内的答案就是次大值。
并查集维护加边,与当期联通块的情况。加入一个条边,合并两个联通块,对新联通块维护最大值和次大值。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ; struct Node{
int a,b;
}A[N >> ];
int Num[N], fa[N], fir[N], sec[N], tag[N]; int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
int n = read(), cnt = ;
for (int i=; i<=n; ++i) {
A[i].a = read(), A[i].b = read();
Num[++cnt] = A[i].a, Num[++cnt] = A[i].b;
}
sort(Num + , Num + cnt + );
int lim = cnt;cnt = ;
for (int i=; i<=lim; ++i) if (Num[i] != Num[cnt]) Num[++cnt] = Num[i];
for (int i=; i<=n; ++i) {
A[i].a = lower_bound(Num + , Num + cnt + , A[i].a) - Num;
A[i].b = lower_bound(Num + , Num + cnt + , A[i].b) - Num;
}
for (int i=; i<=cnt; ++i) fa[i] = i, fir[i] = Num[i];
for (int i=; i<=n; ++i) {
int u = find(A[i].a), v = find(A[i].b);
if (u != v) {
fa[v] = u; tag[u] |= tag[v];
if (fir[v] > fir[u]) sec[u] = max(fir[u], sec[v]), fir[u] = fir[v];
else sec[u] = max(sec[u], fir[v]);
}
else if (tag[u]) {
puts("-1"); return ;
}
else tag[u] = ;
}
int Ans = ;
for (int i=; i<=cnt; ++i) {
if (i == find(i)) {
if (tag[i]) Ans = max(Ans, fir[i]);
else Ans = max(Ans, sec[i]);
}
}
cout << Ans; return ;
}