题目链接
分析
桶排序
不要二分图，不要并查集
这个题最开始感觉读起来不是很难，起码一眼能看懂题意，就是给定(n)个数对，每个数对里边只能取1个数，构成数列{1……i}，问(i)的最大值是多少，最开始想的是把数对排个序，然后从1开始取，看看能取到几，但发现(sort)的时间复杂度对这道题来说不可，但我就想排序，怎么办呢？于是这个时候就用到了一个时间复杂度为(O(n))的排序算法，桶排序。
然后我们只需要遍历一遍每个桶就好，但是有两个数，放哪个数还是要考虑考虑的，如果两个数都没有放过，肯定是放小的那个，因为放了大的也没用，答案更新不到它那边，如果有一个放了，肯定就放另一个，不放白不放啊。
于是，就有了下边的AC代码。。。。
但其实这个类似贪心的算法还是有问题的，问题解决可能还需要(sort)，然后时间复杂度又回去了。
#include<cstdio>
#include<algorithm>
const int N=1e6+10;
int p[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
if(!p[a]&&!p[b])p[std::min(a,b)]++;
else if(p[a])p[b]++;
else p[a]++;
}
for(int i=1;i<=n+1;i++)
if(!p[i]){
printf("%d
",i-1);
return 0;
}
}
并查集
我们可以把每组输入转化成边，然后用并查集进行维护，最后判断一下输出就行。
#include<cstdio>
#include<cstring>
const int N=1e6+10;
int f[N],w[N],isc[N];
int find(int x){
return f[x]==x?x:(f[x]=find(f[x]));
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n+1;i++)f[i]=i;
for(int i=1;i<=n+1;i++)w[i]=1;
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
int fa=find(a),fb=find(b);
if(fa==fb)isc[fa]=1;
else {
isc[fa]|=isc[fb];
isc[fb]=0;
w[fa]+=w[fb];w[fb]=0;
f[fb]=fa;
}
}
int ans;
for(int i=1;i<=n+1;i++)
if(!isc[find(i)]){
if(w[find(i)]==1){
ans=i-1;break;
}else w[find(i)]--;
}
printf("%d
",ans);
}
二分图匹配
首先来说什么叫二分图，二分图简单来说就是不含奇数环的点，判断一张图是不是二分图的话，常用的是染色法，这道题就用到了。
再说什么叫二分图匹配，二分图匹配说白了就是给一个男孩子集合，给定几组喜欢关系，在另外一个女孩子集合找一个点进行配对，跟函数里边的对应关系差不多。
什么叫二分图的最大匹配呢，就是让能找到女孩子的男孩子尽量都找到。
二分图的完美匹配呢？（虽然和这题没什么关系吧）就是让所有的男孩子和女孩子都成对。
这道题如果闭着眼跑一个二分图的最大匹配，你会发现WA了。
于是我们需要睁开眼跑二分图的最大匹配，但仍然会T掉，为什么呢，因为匹配了很多没有意义的匹配。
其实这个题用匈牙利算法直接匹配就行了，但是怎么建图呢？
我们看这个图，匹配的时候从(u)中取出一个值去匹配(v)中的值，因为你不能把两个男孩子跟一个女孩子配对（这不乱了吗），所以就是一对一匹配，因为每个数对只能取一个，所以可以把这两个数都加到(u)中，(v)中放上从(1-n)，然后从小到大匹配就行，如果遇到不能匹配的点，输出就行。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct Edge{
int to,nxt;
}e[N<<1];
int h[N],idx;
void Ins(int a,int b){
e[idx].to=b;e[idx].nxt=h[a];h[a]=idx++;
}
int vis[N],match[N],rt;
bool dfs(int x){
for(int i=h[x];~i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]!=rt){
vis[v]=rt;
if(match[v]==-1||dfs(match[v])){
match[v]=x;
return 1;
}
}
}
return 0;
}
int main(){
memset(h,-1,sizeof(h));
memset(match,-1,sizeof(match));
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
Ins(a,i);Ins(b,i);
}
for(int i=1;i<=10001;i++){
rt=i;
if(!dfs(i)){
printf("%d
",i-1);
return 0;
}
}
}
注意vis数组不能每次都memset，不然肯定会T掉。