题意

• 有n个二元组，每个二元组可以选取一个值，组成一个长为n的序列，问从1开始的最大连通能到几

思路

• 并查集，对于单一二元组，我们总希望选择其中小的

• 对于一个连通块：一定属于下述两种情况之一

  • n个数的连通块，有n-1条边，则最大的元素选不到
  • n个数的连通块，有超过n-1条边，则所有元素均可选到

• 所以，读入一个二元组后，总可以把小的元素所属的连通块合并到大的元素所属的连通块之中，同时，把小的元素所属的连通块的父亲标记成可以选取，维护并查集。

• 特别的，如果两个元素本身就属于一个连通块之中，说明变味了情况二，直接把整个连通块的父亲标为可选

• 最终，从1开始找第一个没被标记的即为最大连击

另一种说法

• 每次输入把这两个数整合在一个集合
• 如果之前这两个数已经在一个集合，说明较小的数一定可以被选上，不管是前一次或者当前这次，所以直接把这个小数打上标记
• 如果不在一个集合，把小数的集合指向大数的集合，并且把小数打上标记，因为选取的话一定先挑小的选
• 最后遍历全部的数，哪个没有被打上标记，就说明整个数无法被选上了，最多的连击数就是i−1

AC代码

#include<bits/stdc++.h>
using namespace std;
int fa[1010101],vis[1010101];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<10010;i++) fa[i]=i;
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x=find(x);y=find(y);
        if(x==y) vis[x]=1;
        else{
            if(x>y) swap(x,y);
            fa[x]=y;
            vis[x]=1;
        }
    }
    int i=1;
    for(;vis[i]==1;i++);
    printf("%d\n",i-1);
    return 0;
}