【题目】
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<=1000
对于100%的数据，保证N<=1000000
【算法分析】
做法1：
这是通法~
我们把那个10000个数字放在二分图的左边，然后把武器放在二分图的右边。
对于一个武器，连左边两个对应的点。
然后从左边的点1开始一直像正常的匹配那样搞下去，直到某一个地方，找不到增广路，证明前i个点不能被同时满足了。那么输出i-1即可。
做法2：
这个我觉得并不容易想到。
把那10000个点看成点。
然后武器看成无向边。
(1)对于一个联通块，假如不含环（就是一棵树），那么必定可以满足其中任意的p-1个点。
(2)对于一个联通块，假如含环，那么必定全部的p个点都能满足。
如此用并差集维护即可。
对(1)容易用数学归纳法证明。
对(2)，可以通过(1)来证明。
【其他】
实际测试表明，匹配和并差集的速度差不多。
注：并差集用的IO外挂，所以速度会快很多，实际上去掉以后速度是差不多的。
【CODE——匹配】
#include
struct gtp{int y,next;}g[N*2];
int n,e;
int a[N*2][2],v[N*2],ls[10005],link[N*2];
inline void addedge(int x,int y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}
bool find(int p,int kk){
int q;
for (int t=ls[p];t;t=g[t].next)
if (v[g[t].y]!=kk){
v[g[t].y]=kk;
q=link[g[t].y];
link[g[t].y]=p;
if (!q || find(q,kk)) return true;
link[g[t].y]=q;
}
return false;
}
void solve(){
e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++){
addedge(a[i][0],i);
addedge(a[i][1],i);
}
for (int i=1;i<=10001;i++){
if (!find(i,i)){
printf("%dn",i-1);
return;
}
}
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i][0],&a[i][1]);
solve();
}
【CODE——并差集】
#include
int n;
int f[N],v[N];
char ch;
int gf(int p){
if (f[p]==p) return p;
return f[p]=gf(f[p]);
}
inline void Read(int &x){
x=0;
ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
while (ch!=’ ‘ && ch!=’n’){
x=x*10+ch-‘0’;
ch=getchar();
}
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int x,y,i,tmp;
for (i=1;i<=N;i++){
f[i]=i;
v[i]=0;
}
Read(n);
for (i=1;i<=n;i++){
Read(x); Read(y);
if (gf(x)!=gf(y)){
if (f[x]>f[y]){tmp=x; x=y; y=tmp;}
v[f[y]]|=v[f[x]];
f[f[x]]=f[y];
}else v[f[x]]=1;
}
for (i=1;i
printf("%dn",i-1);
break;
}
}