Poj1733 Parity game & Poj1182 食物链 — 并查集的扩展域方法

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

Poj1733：

1. 把问题转化为并查集模型：
a b even等价于(0..a-1)与(0..b)同奇同偶
a b odd等价于(0..a-1)与(0..b)不同奇不同偶
我们用same和diff两个数组来代表每个点的相同和不同，比如令same[i]=i,diff[i]=i+10000(这个你随便加啦，只要不重复就好)。
对于集合的合并：
对于a b even,就union(same(a-1),same(b))，union(diff(a-1),diff(b))，表示a~b有偶数个的话，0~a-1必然和0~b是同奇同偶或异奇异偶。
对于a b odd,则union(same(a-1),diff(b))，union(diff(a-1),same(b))。
对于判断是否合法：
a b even，则find(same(a-1))=find(same(b))，此时必然同时有find(diff(a-1))=find(diff(b))
a b odd，则find(diff(a-1))=find(same(b))，此时必然同时有find(same(a-1))=find(diff(b))
这样就可以判断了.循环每个提问,先判断,不符合就writeln&break, 否则union;

2. 解决01串长的问题——利用哈希表：
经过上面的分析还是不行，01串长度为十亿，你直接存必然MLE，但注意到问答之后5000个所以使用哈希表(开散列)，mod一个数，比如10009这样的质数。
这样的话经过映射就解决啦！不多说了，还不懂的话，去看程序。
总的来说，这道题综合了并查集和哈希表，而且需要一番思考才可以转化，是一道很有价值的题！

Source Code

Problem: 1733		User: lydliyudong
Memory: 1600K		Time: 63MS
Language: Pascal		Result: Accepted

• Source Code

var
 same,diff,link,next:array[0..20000]of longint;
 fa:array[0..40000]of longint;
 head:array[0..99990]of longint;
 n,q,a,b,a1,b1,a2,b2,i,tot:longint;
 ch:char;

function find(x:longint):longint;
 begin
  if x=fa[x] then exit(x);
  fa[x]:=find(fa[x]);
  exit(fa[x]);
 end;

function hash(x:longint):longint;
 var
  i,p:longint;
 begin
  p:=x mod 99991;
  i:=head[p];
  while i<>0 do
   begin
    if link[i]=x then exit(i);
    i:=next[i];
   end;
  inc(tot);
  link[tot]:=x;
  next[tot]:=head[p];
  head[p]:=tot;
  exit(tot);
 end;

begin
 readln(n,q);
 if q=0 then writeln(0); 
 for i:=0 to 40000 do fa[i]:=i;
 for i:=0 to 20000 do begin same[i]:=i; diff[i]:=i+20000; end;
 for i:=1 to q do
  begin
   readln(a,b,ch,ch);
   dec(a);
   a:=hash(a);
   b:=hash(b);
   a1:=find(same[a]);
   a2:=find(diff[a]);
   b1:=find(same[b]);
   b2:=find(diff[b]);
   case ch of
    'o':
     begin
      if (a1=b1)or(a2=b2) then begin writeln(i-1); break; end;
      fa[a1]:=b2;
      fa[a2]:=b1;
     end;
    'e':
     begin
      if (a1=b2)or(a2=b1) then begin writeln(i-1); break; end;
      fa[a1]:=b1;
      fa[a2]:=b2;
     end;
   end;
   if i=q then writeln(q);
  end;
end.

Poj1182：

维护三个域：同类域（自身域）、吃域、被吃域。

若A吃B，B吃C，C吃A，则A的吃域=B的同类域=C的被吃域，A的被吃域=C的同类域=B的吃域，A的同类域=C的吃域=B的被吃域。

只需要通过维护这些域之间的关系便可判断生物之间的关系。

Source Code

Problem: 1182		User: lydliyudong
Memory: 1476K		Time: 204MS
Language: Pascal		Result: Accepted

• Source Code

var
 fa:array[0..150000]of longint;
 n,m,x,y,z,x1,x2,x3,y1,y2,y3,ans,i:longint;
function find(x:longint):longint;
 begin
  if fa[x]=x then exit(x);
  fa[x]:=find(fa[x]);
  exit(fa[x]);
 end;
begin
 read(n,m);
 for i:=1 to 3*n do fa[i]:=i;
 for i:=1 to m do
  begin
   read(z,x,y);
   if (x>n)or(y>n) then begin inc(ans); continue; end;
   x1:=find(x); x2:=find(x+n); x3:=find(x+2*n);
   y1:=find(y); y2:=find(y+n); y3:=find(y+2*n);
   case z of
    1:
     begin
      if (x1=y2)or(y1=x2) then inc(ans)
      else begin
       fa[x1]:=y1;
       fa[x2]:=y2;
       fa[x3]:=y3;
      end;{else}
     end;
    2:
     begin
      if (x1=y1)or(x1=y2) then inc(ans)
      else begin
       fa[y1]:=x2;
       fa[y3]:=x1;
       fa[x3]:=y2;
      end;{else}
     end;
   end;{case}
  end;
 writeln(ans);
end.