题目链接

分析

桶排序

不要二分图，不要并查集
这个题最开始感觉读起来不是很难，起码一眼能看懂题意，就是给定\(n\)个数对，每个数对里边只能取1个数，构成数列{1……i}，问\(i\)的最大值是多少，最开始想的是把数对排个序，然后从1开始取，看看能取到几，但发现\(sort\)的时间复杂度对这道题来说不可，但我就想排序，怎么办呢？于是这个时候就用到了一个时间复杂度为\(O(n)\)的排序算法，桶排序。
然后我们只需要遍历一遍每个桶就好，但是有两个数，放哪个数还是要考虑考虑的，如果两个数都没有放过，肯定是放小的那个，因为放了大的也没用，答案更新不到它那边，如果有一个放了，肯定就放另一个，不放白不放啊。
于是，就有了下边的AC代码。。。。

#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\n",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\n",ans);
}

二分图匹配

本人还没有学会，学会再补

[SCOI2010]连续攻击游戏 思维

原文：https://www.cnblogs.com/anyixing-fly/p/12822396.html