家谱并差集

题意/Description：

现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

读入/Input：

输入文件由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name 的形式描写一组父子关系中的父亲的名字，用+name 的形式描写一组父子关系中的儿子的名字；接下来用?name 的形式表示要求该人的最早的祖先；最后用单独的一个 $表示文件结束。规定每个人的名字都有且只有 6 个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有 1000 组父子关系，总人数最多可能达到 50000 人，家谱中的记载不超过 30 代。

输出/Output：

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

题解/solution：

题目很简单，第一眼看就是并差集，小case啦。后来才发现不是就是Time Limit Exceed就是Wrong Answer。所以我们开个哈希表来储存名字（最好把字符转化为数字），可以加快速度。然后才发现哈希表不能太大，当然不能太小。就对了。

代码/Code：

var
  h2:array [0..150000] of longint;
  h1:array [0..150000] of string;
  f:array [0..60001] of string;
  a:array [0..60001] of longint;
  t1,t2,k:longint;
  s:string;
  c:char;
function hash(s:string):longint;
var
  i:longint;
begin
  hash:=0;
  for i:=1 to length(s) do
    hash:=hash*4+ord(s[i]);
end;

function fd(s:string):longint;
var
  x:longint;
begin
  x:=hash(s);
  while h1[x]<>'' do
    begin
      if h1[x]=s then exit(h2[x]);
      inc(x);
      if x>150000 then x:=0;
    end;
  exit(0);
end;

procedure ins(s:string;a:longint);
var
  i,x:longint;
begin
  x:=hash(s);
  while h1[x]<>'' do
    begin
      inc(x);
      if x>150000 then x:=0;
    end;
  h1[x]:=s; h2[x]:=a;
end;

function find(x:longint):longint;
var
  y,t,k:longint;
begin
  y:=x;
  while a[y]>0 do
    y:=a[y];
  k:=y;
  y:=x;
  while a[y]>0 do
    begin
      t:=a[y];
      a[y]:=k;
      y:=t;
    end;
  find:=k;
end;

procedure union(x,y:longint);
var
  u,v:longint;
begin
  u:=find(x);
  v:=find(y);
  a[v]:=u;
end;

procedure init;
var
  i:longint;
begin
  for i:=1 to 150000 do
    begin
      h1[i]:=''; h2[i]:=0;
    end;
  while 1=1 do
    begin
      readln(s);
      if s='$' then halt;
      c:=s[1]; delete(s,1,1);
      t1:=fd(s);
      if t1=0 then
        begin
          inc(k); f[k]:=s; t1:=k; ins(s,k);
        end;
      if c='#' then
        t2:=t1;
      if c='+' then
        union(t2,t1);
      if c='?' then
        begin
          writeln(s,' ',f[find(t1)]);
        end;
    end;
end;

begin
  init;
end.

家谱 并差集

家谱并差集