[vijos P1034] 家族

寒假给自己定的第一个目标就是把并查集，Tarjan之类搞会。翻了翻笔记，发现并查集是2012年的6月30日学的…早就忘光了…今天敲题目的时候也吃了不少的亏呢…

家族这一题就是并查集的标准题，第一次提交失误了，我的union子过程莫名陷入了死循环，我的f数组存在死循环，最后发现是find函数有个bug…

我又跑去参考NOCOW了，只是觉得一直参考标程不是太好，毕竟比赛的时候得独立debug是吧…

核心代码就是union子过程和find函数了，其实也没什么技术含量，思路比较要紧。过会儿去研究下，这个算法貌似还有什么优化来着~

program vijos_p1034;

var f:array[..] of integer;

    i,j,n,p,m,mi,mj,li,lj,pi,pj:integer;

function find(x:integer):integer;

var t:integer;

begin

  if f[x]=x then exit(x) else f[x]:=find(f[x]);

  exit(f[x]);

end;

procedure union(x,y:integer);

var fx,fy:integer;

begin

  fx:=find(x);

  fy:=find(y);

  if fx<>fy then f[fx]:=fy;

end;

begin

  readln(n,m,p);

  for i:= to n do

    f[i]:=i;

  for i:= to m do

    begin

      readln(mi,mj);

      union(mi,mj);

    end;

  for i:= to p do

    begin

      readln(pi,pj);

      li:=find(pi);

      lj:=find(pj);

      if li=lj then writeln('Yes') else writeln('No');

    end;

end.

家族