POJ 1635 Subway tree systems 有根树的同构

POJ 1635

题目很简单 给个3000节点以内的根确定的树 判断是否同构。用Hash解决，类似图的同构，不过效率更高。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<vector>

#include<cmath>

#include<vector>

using namespace std;

typedef unsigned long long int ULL;

const ULL leaf_hash=2099,pt=9907099,qt=9907099;

const int maxn=3000+1;

char str1[maxn],str2[maxn] ;

char *p;

ULL Hash()

{

 ULL sum=1;

 if(*(p)=='1'&&*(p-1)=='0')

 	{

 	 p++;

 	 return leaf_hash;

	}

 while(*p!='\0'&&*p++=='0')//这个巧妙的循环,把子节点的hash值都加给了父节点,作为父节点的hash值

     {

     	sum=(sum*(pt^Hash()))%qt;

	 }

 return sum;

}

int main()

{

 int T;scanf("%d",&T);

 while(T--)

 	{

 	 scanf("%s%s",str1,str2);

 	 p=str1;

 	 ULL a=Hash();

 	 p=str2;

 	 ULL b=Hash();

 	 if(a==b)puts("same");

			else  puts("different");

	}

 return 0;

}