首页 > 代码库 > SDOI2008Cave 洞穴勘测

SDOI2008Cave 洞穴勘测

2024-07-08 20:03:30   252人阅读

无限膜拜CLJ大牛……

不会动态树的弱弱在CLJ的帮助下AC了此题

我想到了并查集（人人都会想到的吧……囧），但不知道应该如何处理destroy操作……

其实 make操作的实质就是：把x节点到其所在集合代表元的路上所有有向边都反过来，然后就可以处理本体所需的所有操作了（自己想想为何）。

代码：

 1 var i,n,m,x,y:longint; 2     ch,cha:char; 3     fa:array[0..210000] of longint; 4 function find(x:longint):longint; 5  begin 6    while x<>fa[x] do x:=fa[x]; 7    exit(x); 8  end; 9 procedure make(x:longint);10  var y,tmp:longint;11  begin12  y:=fa[x];fa[x]:=x;13  while y<>x do14   begin15   tmp:=fa[y];fa[y]:=x;16   x:=y;y:=tmp;17   end;18  end;19 procedure connect(x,y:longint);20  begin21  make(x);make(y);22  fa[x]:=y;23  end;24 procedure destroy(x,y:longint);25  begin26  make(x);27  fa[y]:=y;28  end;29 procedure query(x,y:longint);30  begin31  if find(x)<>find(y) then writeln(‘No‘) else writeln(‘Yes‘);32  end;33 procedure main;34  begin35    readln(n,m);36    for i:=1 to n do fa[i]:=i;37    for i:=1 to m do38     begin39      read(ch);cha:=‘a‘;while cha<>‘ ‘ do read(cha);readln(x,y);40      if ch=‘C‘ then connect(x,y)41      else if ch=‘D‘ then destroy(x,y)42      else query(x,y);43     end;44  end;45 46 begin47  main;48 end.
View Code

最后我想说一句：并查集还大有文章可做！


联系
我们