【BZOJ4474】isomorphism（树的同构，哈希）

题意：一个无向树的度数为 2的结点称为假结点，其它结点称为真结点。一个无向树的简化树
其结点由原树的全体真结点组成，两个真结点之间有边当且仅当它们在原树中有边，或者在
原树中有一条联结这两个结点的路，其中间节点全是假结点。两个无向树各自的简化树如果
同构，即存在结点之间的一一对应，使得在一个树中的任意两个结点之间有边当且仅当它们
的对应结点在另一个树中有边，则称原来的两个无向树实质同构。给定若干个无向树，将相
互实质同构的无向树只保留一个其余删除。统计剩下的相互不实质同构的无向树个数，并将
它们的简化树结点个数从小到大输出。

cas<=20 n<=10000

思路：把很久以前在另一个地方写的题解搬过来

定义题。做法请看题目。

删除假节点并连边：先按输入构图并统计每个点的度数找一个度不为2的点做一遍dfs

if d[v]=2 f[find(u)]=f[find(v)]

做完之后重连所有f[x[i]]<>f[y[i]]的边

同构：

哈希，将点上的哈希初值都=1，对于点u，取与u相连的点权V并排序，随意哈希作为新的哈希值。迭代10000000000000000000000000000000次。最后只需判断哈希值是否相等。

 const mo=;

 var head,vet,next,d,b,x,y,e1,q,f:array[..]of longint;

     hash,s,c,h:array[..]of int64;

     cas,v1,e,v,i,tot,len,n,j,k,ans:longint;

     tmp:int64;

     p:boolean;

 procedure qsort(l,r:longint);

 var i,j:longint;

     t,mid:int64;

 begin

  i:=l; j:=r; mid:=q[(l+r)>>];

  repeat

   while mid>q[i] do inc(i);

   while mid<q[j] do dec(j);

   if i<=j then

   begin

    t:=q[i]; q[i]:=q[j]; q[j]:=t;

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 function find(k:longint):longint;

 begin

  if f[k]<>k then f[k]:=find(f[k]);

  find:=f[k];

 end;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 procedure dfs(u,fa:longint);

 var e,v:longint;

 begin

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then

   begin

    if d[v]= then f[find(v)]:=f[find(u)];

    dfs(v,u);

   end;

   e:=next[e];

  end;

 end;

 begin

  readln(cas);

  for v1:= to cas do

  begin

   read(n);

   fillchar(head,sizeof(head),);

   fillchar(b,sizeof(b),);

   fillchar(d,sizeof(d),);

   for i:= to n do hash[i]:=;

   for i:= to n do f[i]:=i;

   tot:=;

   for i:= to n- do

   begin

    read(x[i],y[i]);

    inc(d[x[i]]); inc(d[y[i]]);

    add(x[i],y[i]);

    add(y[i],x[i]);

   end;

   for i:= to n do

    if d[i]<> then

    begin

     dfs(i,-);

     break;

    end;

   tot:=;

   fillchar(head,sizeof(head),);

   for i:= to n- do

    if f[x[i]]<>f[y[i]] then

    begin

     b[f[x[i]]]:=; b[f[y[i]]]:=;

     add(f[x[i]],f[y[i]]);

     add(f[y[i]],f[x[i]]);

    end;

   for i:= to n do

    if d[i]<> then inc(e1[v1]);

   for i:= to  do

   begin

    for j:= to n do h[j]:=hash[j];

    for j:= to n do

     if b[j]= then

     begin

      e:=head[j];

      len:=;

      while e<> do

      begin

       v:=vet[e];

       inc(len); q[len]:=h[v];

       e:=next[e];

      end;

      if len> then qsort(,len);

      tmp:=;

      for k:= to len do tmp:=(tmp*+q[k]) mod mo;

      hash[j]:=tmp;

     end;

   end;

   len:=;

   for i:= to n do

    if b[i]= then begin inc(len); q[len]:=hash[i]; end;

   if len> then qsort(,len);

   tmp:=;

   for i:= to len do tmp:=(tmp*+q[i]) mod mo;

   s[v1]:=tmp;

  end;

  for i:= to cas do

  begin

   p:=true;

   for j:= to i- do

    if s[i]=s[j] then

    begin

     p:=false; break;

    end;

   if p then begin inc(ans); c[ans]:=e1[i]; end;

  end;

  for i:= to ans do q[i]:=c[i];

  qsort(,ans);

  writeln(ans);

  for i:= to ans- do write(q[i],' ');

  write(q[ans]);

 end.

巴特西

【BZOJ4474】isomorphism（树的同构，哈希）

最新文章

热门文章