[文章目录]
Description
给你n个二元组。你可以使用一些二元组中的一个值，当一个二元组中一个值被你使用之后，另一个将不能被使用。问组成友谊开始连续的正整数的最长长度。
一眼匈牙利，二元组中的数向二元组连边，从1开始找增广路径，一旦找不到即为最长长度。
但是还有更优秀的做法。将二元组(a,b)看成a向b连的一条边。那么假设出现一个双联通分量的话，我们一定能满足其中所有点。假设是一个树的话，我们贪心满足编号小的点，显然存在方法使得只有最大的编号那个点没有满足。用并查集维护，合并树的时候将编号大的点作为整个的标记，如果两个点已经联通，说明最大点也满足了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,fa[10100];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
bool vis[10100];
int main()
{
for(int i=1;i<=10000;++i) fa[i]=i;
scanf("%d",&n); int x,y;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
x=find(x); y=find(y);
if(x==y) vis[x]=1;
else
{
if(x<y) swap(x,y);
vis[y]=1; fa[y]=x;
}
}
for(int i=1;i<=10001;++i) if(!vis[i])
{
printf("%d\n",i-1);
return 0;
}
}