落红逐青裙

树的同构判定的两种方法

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

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

#include <stdio.h>
#include<stdlib.h>
int h[9999];
char s[9999],t[9999],*p;
int hash(int j)
{
int sum=h[j+5000];
while (*p && *p++=='0')
sum=(sum+h[j]*hash(j+1)) % 19001;
return ((sum*sum) % 19001);
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<9999;i++)
h[i]=rand()%19001;
while (n--)
{
scanf("%s%s",s,t);
p=s;
i=hash(0);
p=t;
printf("%sn",i==hash(0)?"same":"different");
//可以多次hash，避免冲突
}
return 0;
}

普通方法

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
struct node
{
bool visited;
int no;
node* first;
node* next;
};
char w1[3010],w2[3010];
inline void init(node* x)
{
x->visited=0;x->no=0;
x->first=NULL;x->next=NULL;
}
inline void creat(node*& x,char *str,int& s)
{
if(str[s]=='') return ;
if(str[s]=='0')
{
x=new node;
init(x);
x->no=s;
s++;
creat(x->first,str,s);
node *p=x;
while(p->next) p=p->next;
creat(x->next,str,s);
}
else s++;
}
inline int cal(node *x)
{
int sum=0;
if(x==NULL) return 0;
node *p=x->first;
while(p)
{
sum+=cal(p);
p=p->next;
}
x->no=sum+1;
x->visited=0;
return x->no;
}
inline void setvisit(node *p,bool tag)
{
if(p==NULL) return ;
node *q=p->first;
while(q)
{
setvisit(q,tag);
q=q->next;
}
p->visited=tag;
}
inline void tsort(node *x)
{
if(x==NULL || x->no==1)
return ;
node *p=x->first;
while(p)
{
tsort(p);
p=p->next;
}
node *q=x->first->next;
x->first->next=NULL;
while (q!=NULL)
{
node *temp=q->next;
node** r=&x->first;
while (*r!=NULL && (*r)->no < q->no)
r=&((*r)->next);
q->next=(*r);
*r=q;
q=temp;
}
}
bool comp(node *x,node *y)
{
if(x==NULL && y==NULL)
return true;
if(x==NULL || y==NULL)
return false;
if(x->no!=y->no)
return false;
node *p=x->first;
node *q;
while(p!=NULL)
{
q=y->first;
while(q)
{
if(q->visited==false && comp(p,q))
{
q->visited=true;break;
}
else if(q->visited==false)
{
setvisit(q,false);
}
q=q->next;
}
if(q==NULL)
return false;
p=p->next;
}
return true;
}
inline void del(node *x)
{
if(x==NULL) return;
node *p=x->first;
while(p)
{
node* q=p->next;
del(p);
p=q;
}
delete p;
x->first=NULL;
}
int main()
{
int t;
node t1,t2;
int n=0;
bool flag;
scanf("%d",&t);getchar();
while(t--)
{
scanf("%s %s",w1,w2);
n=0;creat(t1.first,w1,n);
n=0;creat(t2.first,w2,n);
cal(&t1);cal(&t2);
tsort(&t1);tsort(&t2);
flag=comp(&t1,&t2);
del(&t1);del(&t2);
if(flag) printf("Truen");
else printf("Falsen");
}
return 0;
}

hash, 树的同构

No Comments

TC初次

Posted by twcai in TopCoder on July 11, 2008

初次听说TopCoder是在大一的时候去ZJU的ZJG校区听薛在岳大牛的ACM讲座，时隔那么久，我还是小菜菜一个，不过今晚和一起参加ACM的室友一起注册了TC的SRM409。
C++还没学好，250分的题目我花了20分钟左右才写好，交了一下，147.93分。
challenge phase阶段，我成功cha掉房间里最菜的250，不过又失败了两次，就收手了，呵呵
发现Topcoder很有意思

SRM

No Comments