Description
lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有\(2\)个属性，这些属性的值用\([1,10000]\)之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从\(1\)开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为\(1\)的装备攻击boss，然后只能使用某个属性值为\(2\)的装备攻击boss，然后只能使用某个属性值为\(3\)的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？
Input
输入的第一行是一个整数N，表示lxhgww拥有N种装备 接下来\(N\)行，是对这N种装备的描述，每行\(2\)个数字，表示第i种装备的\(2\)个属性值
Output
输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。
Sample Input
3
1 2
3 2
4 5
Sample Output
2
HINT
对于\(30\%\)的数据，保证\(N \le1000\)
对于\(100\%\)的数据，保证\(N \le1000000\)
这道题很明显可以用二分图最大匹配来跑。每件武器像其两个属性值连边，依次顺序枚举属性值。若某个属性值无法进行匹配，则输出答案即可。
但是这题有个更优美的算法：并查集。
这个做法是在HZWER的博客里面看到的：每个装备我们把它想象成一条边，两个属性值把它想象成这条边连接的两个点。
那么，如果一个联通块中有\(n\)个点，无环，说明只有\(n-1\)条边，\(n-1\)件装备，无法把整个联通块的属性值都选择。由于我们要通过尽可能多的关卡，我们肯定就不选属性值最大的那个点。
如果这个联通块中有环，边数\(E\)一定会$ \ge \(点数\)V$，说明这个所有点都可以被选择到。
这些我们都可以用并查集来维护。
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define maxn 1000010
int father[maxn],n;
bool vis[maxn];
inline int find(int a)
{
if (father[a] != a) father[a] = find(father[a]);
return father[a];
}
inline void Union(int a,int b)
{
if (a > b)
swap(a,b);
vis[a] = true;
father[a] = b;
}
int main()
{
scanf("%d",&n);
int i,a,b;
for (i = 1;i<=n+1;++i)
father[i] = i;
for (i = 1;i<=n;++i)
{
scanf("%d %d",&a,&b);
int r1 = find(a),r2 = find(b);
if (r1 == r2) vis[r1] = true;
else Union(r1,r2);
}
for (i = 1;i<=n+1;++i)
if (!vis[i])
{printf("%d",i-1);break;}
return 0;
}
