Educational Codeforces Round 49 Problem F

未分类

题意：
有$n$门课程，每门课程可以在第$a_i$或$b_i$天完成考试，限制一天最多只能完成一门考试，最早什么时候可以完成所有考试？
数据范围：$(1\leq n \leq 10^6,1\leq a_i<b_i\leq 10^9)$

解析：
把每天看做一个点，每门课程看成一条边，对所有$a_i,b_i$连边，那么就是为每条边分配一个端点，每个点最多只能被分配给一条边。考虑同一个联通块：
１、如果联通块里有恰好$n-1$条边（树），那么显然把时间最大的点当根，$dfs$一下，每条边分配给相应的儿子节点，也就是最优情况是把时间最大的点去掉。
２、如果联通块有$n$条边（基环树），那么所有时间点都需要被用上，同时也显然能构造出可行解。
３、如果联通块有$n$条以上的边，显然会导致无解。
用并查集跑一下即可。

原题链接：http://codeforces.com/problemset/problem/1027/F
参考$AC$代码：http://codeforces.com/contest/1027/submission/41906486