题意:
有n场考试，给出每场考试的\(a_i, b_i\)值， \(a_i < b_i\), \(a_i, b_i\)代表这场考试可以考的时间，问最少需要多少天来考完n场考试，如果不能考完就输出-1
思路:
先介绍一下整体思路，将\(a_i, b_i\)连边，连通块里面的边和点的情况可以分为3中情况
- 边 == 点数，对于这种情况，取里面的最大值
- 边 == 点数 + 1，对于这种情况，取次大值
- 边 > 点数，对于这种情况是不可能的，直接输出-1
对于这种两个两个联动，考虑下并查集，就用并查集来实现一个连边的操作， 这里用到了连通块的思想，连通块图论可以处理，并查集也可以处理， 然后边 == 点数，可以用一个tag标记来实现，边数 > 点数，那就是在已经有环的基础上，又有一个环，还是用tag来标记实现，求每个点的最大值和最小值，可以利用类似dp的思想，先赋初值，然后在在求解， 最后ans再取最大值即可
总结:
并查集判断实现边点关系，求一个连通块中的最大值和次大值
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 10;
ll n;
ll fa[MAXN << 1], firmx[MAXN << 1], secmx[MAXN << 1], tag[MAXN << 1];
struct Node
{
ll a, b;
} w[MAXN];
ll find(ll x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> n;
vector<ll> num;
for (int i = 0, a, b; i < n; ++i)
{
cin >> w[i].a >> w[i].b;
num.emplace_back(w[i].a);
num.emplace_back(w[i].b);
}
sort(num.begin(), num.end());
auto newend = unique(num.begin(), num.end());
num.erase(newend, num.end());
for (int i = 0; i < n; ++i)
{
w[i].a = lower_bound(num.begin(), num.end(), w[i].a) - num.begin();
w[i].b = lower_bound(num.begin(), num.end(), w[i].b) - num.begin();
}
for (int i = 0; i < num.size(); ++i)
fa[i] = i, firmx[i] = num[i];
for (int i = 0; i < n; ++i)
{
ll u = find(w[i].a), v = find(w[i].b);
if (u != v)
{
fa[v] = u, tag[u] |= tag[v];
if (firmx[v] > firmx[u])
secmx[u] = max(secmx[v], firmx[u]), firmx[u] = firmx[v];
else
secmx[u] = max(secmx[u], firmx[v]);
}
else if (tag[u])
puts("-1"), exit(0);
else
tag[u] = 1;
}
ll ans = 0;
for (int i = 0; i < num.size(); ++i)
{
if (i == find(i))
{
if (tag[i])
ans = max(ans, firmx[i]);
else
ans = max(ans, secmx[i]);
}
}
cout << ans << endl;
return 0;
}