我们可以把一件装备看成一条边,两个属性看成两个点,那么这就相当于读入了一张图
当读入每一个x,y时,我们找到两个点的祖先节点,fx,fy,我们保证祖先节点在该连通块
中编号(装备属性)最大,用flag数组记录能否过第I关,那么两种情况
fx=fy
这种情况就是加入这条边之后,图中成了一个环(可能这个环之前就存在),那么对于
一个环,假设是1-x节点的环,我们肯定可以全选择(题目中的选择),之前假设是一颗树
的话,X个节点,我们可以选择x-1个,也就是只有一个点选不了,我们肯定让最大的
点没法选,所以除了祖先以外应该全都是true,那么加上这条边之后,祖先也可以选了,所以
将祖先也就是flag[fx]设成true
fx<>fy
这种情况就是一条边连接两个连通分量,先假设两个连通分量都是树,那么我们这个新的连通分量也是
一颗树,对于这种情况,我们可以多选择一个没选过的点,也就是在fx,fy中选编号小的设成true,那么如果
两个环的话,这条边就没用了,之前已经可以全选了,那一个环一个树的情况,使fx<fy,对于两个祖先,我们可以
选择一个,那么应该选编号小的,但是如果编号小的已经可以选了(就是在环了),我们就应该将fy设成true,这点
应该注意,网上有的标程没判断这个,也A了,只能说数据弱。。。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n :longint;
x, y :longint;
i :longint;
father :array[..] of longint;
flag :array[..] of boolean;
fa, fb :longint;
procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
begin
read(n);
for i:= to do father[i]:=i;
for i:= to n do
begin
read(x,y);
fa:=getfather(x);
fb:=getfather(y);
if fa=fb then flag[fa]:=true else
begin
if fa>fb then swap(fa,fb);
if not flag[fa] then flag[fa]:=true else flag[fb]:=true;
father[fa]:=fb;
end;
end;
for i:= to n+ do if not flag[i] then break;
writeln(i-);
end.