你有n个物品，每个物品有两个属性，每个物品可以用一次，属性必须从1开始连续使用，问最多用几个物品。
看到这个之后，可能更多想到的是贪心，但是我只能说：数据太水了，我贪心竟然过了，然后随便找了几组数据就卡下去了。
还是直接找正解吧：
建一个图。每错建图，怎么建呢？有属性ai，bi，那么就连一条ai到bi的边，然后呢？进行dfs，如果没有环，如果有环，dfs之后就算了，如果没有环，那么最大的取不到。证明？很好证明，或者说没啥好证明的。想一想就好了。
然后就是并不想建这么多边怎么办。那么我们就可以直接用并查集来维护有无环和是否在一起联通，所以代码如下：
#include <cstdio>
#include <string>
using namespace std;
const int maxn=1e4+10;
int f[maxn];
int h[maxn];
int Find(int a){
return a==f[a]?a:(f[a]=Find(f[a]));
}
int main(){
for(int i=1;i<maxn;i++)
f[i]=i;
int n;
scanf("%d",&n);
int js1,js2;
for(int i=1;i<=n;i++){
scanf("%d%d",&js1,&js2);
if(Find(js1)==Find(js2))
h[Find(js1)]=1;
else{
int fa=js1>js2?Find(js1):Find(js2);
f[Find(js1)]=f[Find(js2)]=fa;
}
}
int ans=1e4;
for(int i=1;i<=10000;i++)
if(!h[Find(i)])
ans=min(ans,Find(i)-1);
printf("%d",ans);
return 0;
}
原文：https://www.cnblogs.com/wish-all-ac/p/12826672.html