Posts Tagged 树的同构

树的同构判定的两种方法

Posted by twcai in ACM/ICPC on August 2, 2008

树的同构判定
hash方法跟普通方法真的差很多……把两种都贴出来看下

  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. int h[9999];
  4. char s[9999],t[9999],*p;
  5. int hash(int j)
  6. {
  7.     int sum=h[j+5000];
  8.     while (*p && *p++=='0')
  9.         sum=(sum+h[j]*hash(j+1)) % 19001;
  10.     return ((sum*sum) % 19001);
  11. }
  12. int main()
  13. {
  14.     int i,n;
  15.     scanf("%d",&n);
  16.     for(i=0;i<9999;i++)
  17.         h[i]=rand()%19001;
  18.     while (n--)
  19.     {
  20.         scanf("%s%s",s,t);
  21.         p=s;
  22.         i=hash(0);
  23.         p=t;
  24.         printf("%sn",i==hash(0)?"same":"different");
  25.         //可以多次hash，避免冲突
  26.     }
  27.     return 0;
  28. }

普通方法

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stdlib.h>
  4. using namespace std;
  5.  
  6. struct node
  7. {
  8.     bool visited;
  9.     int no;
  10.     node* first;
  11.     node* next;
  12. };
  13. char w1[3010],w2[3010];
  14.  
  15. inline void init(node* x)
  16. {
  17.     x->visited=0;x->no=0;
  18.     x->first=NULL;x->next=NULL;
  19. }
  20.  
  21. inline void creat(node*& x,char *str,int& s)
  22. {
  23.     if(str[s]=='') return ;
  24.     if(str[s]=='0')
  25.     {
  26.         x=new node;
  27.         init(x);
  28.         x->no=s;
  29.         s++;
  30.         creat(x->first,str,s);
  31.         node *p=x;
  32.         while(p->next) p=p->next;
  33.         creat(x->next,str,s);
  34.     }
  35.     else s++;
  36. }
  37.  
  38. inline int cal(node *x)
  39. {
  40.     int sum=0;
  41.     if(x==NULL) return 0;
  42.     node *p=x->first;
  43.     while(p)
  44.     {
  45.         sum+=cal(p);
  46.         p=p->next;
  47.     }
  48.     x->no=sum+1;
  49.     x->visited=0;
  50.     return x->no;
  51. }
  52.  
  53. inline void setvisit(node *p,bool tag)
  54. {
  55.     if(p==NULL) return ;
  56.     node *q=p->first;
  57.     while(q)
  58.     {
  59.         setvisit(q,tag);
  60.         q=q->next;
  61.     }
  62.     p->visited=tag;
  63. }
  64.  
  65. inline void tsort(node *x)
  66. {
  67.     if(x==NULL || x->no==1)
  68.         return ;
  69.     node *p=x->first;
  70.     while(p)
  71.     {
  72.         tsort(p);
  73.         p=p->next;
  74.     }
  75.     node *q=x->first->next;
  76.     x->first->next=NULL;
  77.     while (q!=NULL)
  78.     {
  79.         node *temp=q->next;
  80.         node** r=&x->first;
  81.         while (*r!=NULL && (*r)->no < q->no)
  82.             r=&((*r)->next);
  83.         q->next=(*r);
  84.         *r=q;
  85.         q=temp;
  86.     }
  87. }
  88.  
  89. bool comp(node *x,node *y)
  90. {
  91.     if(x==NULL && y==NULL)
  92.         return true;
  93.     if(x==NULL || y==NULL)
  94.         return false;
  95.     if(x->no!=y->no)
  96.         return false;
  97.     node *p=x->first;
  98.     node *q;
  99.     while(p!=NULL)
  100.     {
  101.         q=y->first;
  102.         while(q)
  103.         {
  104.             if(q->visited==false && comp(p,q))
  105.             {
  106.                 q->visited=true;break;
  107.             }
  108.             else if(q->visited==false)
  109.             {
  110.                 setvisit(q,false);
  111.             }
  112.             q=q->next;
  113.         }
  114.         if(q==NULL)
  115.             return false;
  116.         p=p->next;
  117.     }
  118.     return true;
  119. }
  120.  
  121. inline void del(node *x)
  122. {
  123.     if(x==NULL) return;
  124.     node *p=x->first;
  125.     while(p)
  126.     {
  127.         node* q=p->next;
  128.         del(p);
  129.         p=q;
  130.     }
  131.     delete p;
  132.     x->first=NULL;
  133. }
  134.  
  135. int main()
  136. {
  137.     int t;
  138.     node t1,t2;
  139.     int n=0;
  140.     bool flag;
  141.  
  142.     scanf("%d",&t);getchar();
  143.     while(t--)
  144.     {
  145.         scanf("%s %s",w1,w2);
  146.         n=0;creat(t1.first,w1,n);
  147.         n=0;creat(t2.first,w2,n);
  148.         cal(&t1);cal(&t2);
  149.         tsort(&t1);tsort(&t2);
  150.         flag=comp(&t1,&t2);
  151.         del(&t1);del(&t2);
  152.         if(flag) printf("Truen");
  153.         else printf("Falsen");
  154.     }
  155.     return 0;
  156. }

,

No Comments