先讨论有根树的同构：
试图确定两颗树的最小表示，如果最小表示相同则同构。
明确一下树的大小判断标准：
① 根节点度数大的树大
② 根节点度数一样时，将子树排序，然后依次判断每个子树，第一个子树大的树大
复杂度分析：
时间：排序均用快排，compare的复杂度是O(n)，快速排序进行nlogn次compare，排序的复杂度是O(n2logn)更新link的复杂度为O(n2logn)，计算rank的复杂度为O(n2)，总的时间复杂度是O(n2logn)（上述考虑的是最坏情况，实际情况原小于理论值）
有根树的同构pku1635
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
const int Mod = 9901;
const int Max = 3010;
const int Mul = 9110;
vector<int> adj[Max];
int father[Max], hash[Max];
bool cmp(int a, int b)
{
return hash[a]<hash[b];
}
int rebuild(char *str)
{
for(int i=0; i<Max; i++)
adj[i].clear();
for(int i=0, j=1, k=0; str[i]; i++){
if(str[i]=='0'){
adj[k].push_back(j);
father[j]=k;
k=j;
j++;
}
else
k=father[k];
}
return 0;
}
int dfs(int k)
{
int val = 0;
if(adj[k].size()==0)
val=1;
else{
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
hash[j]=dfs(j);
}
sort(adj[k].begin(), adj[k].end(), cmp);
val=1908;
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
val=((val*Mul)^hash[j])%Mod;
}
}
return val;
}
int main()
{
int i,j,n;
char s[Max];
scanf("%d",&n);
while(n--){
int hash1, hash2;
scanf("%s", s); //读入一个01字符串，0代表远离根节点，1代表靠近根节点
rebuild(s);
hash1=dfs(0);
scanf("%s",s);
rebuild(s);
hash2=dfs(0);
printf("%s\n", hash1==hash2?"same":"different");
}
return 0;
}
对于无根树，只要确定一个根，就转换成有根树同构的判断了
将树看成无向图，进行拓扑排序(每次删除度为1的点)，最后剩余1或2个点。
如果是1个点，以该点为根建立有根树
如果是2个点，一棵树以任一点为根建树，另一棵树分别以2个点建立树，判断两次。
2009合肥赛区网络预赛 ustc 1117 Bean Language
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
const int Mod = 9901;
const int Max = 1010; //节点数
const int Mul = 9110;
vector<int> adj[Max];
int g[Max][Max], q[Max], level[Max], visit[Max];
int father[Max], hash[Max], one[2], two[2];
bool cmp(int a, int b)
{
return hash[a]<hash[b];
}
void Top(int n, int x) //拓扑排序找根
{
memset(visit, 0, sizeof(visit));
int head=0, tail=0;
for(int i=0; i<n; i++){
if(g[i][n]==1){
visit[i]=1;
level[tail]=0;
q[tail++]=i;
}
}
while(head<tail){
int now=q[head], l=level[head++];
for(int i=0; i<n; i++)
if(!visit[i] && g[now][i]){
g[i][n]--;
if(g[i][n]<=1){
level[tail]=l+1;
q[tail++]=i;
visit[i]=1;
}
}
}
int l=level[tail-1], k=0;
for(int i=tail-1; level[i]==l; i--){
if(k==0){
one[x]=q[i]; k++;
}
else
two[x]=q[i];
}
}
void build(int root, int n)
{
visit[root]=1;
for(int i=0; i<n; i++){
if(!visit[i] && g[root][i]){
adj[root].push_back(i);
build(i, n);
}
}
}
int dfs(int k)
{
int val = 0;
if(adj[k].size()==0)
val=1;
else{
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
hash[j]=dfs(j);
}
sort(adj[k].begin(), adj[k].end(), cmp);
val=1908;
for(int i=0; i<adj[k].size(); i++){
int j=adj[k][i];
val=((val*Mul)^hash[j])%Mod;
}
}
return val;
}
int main()
{
int i,j,n,cas,a,b;
char s[Max];
scanf("%d",&cas);
while(cas--){
int hash1, hash2;
scanf("%d",&n); //读入n个节点
memset(g, 0, sizeof(g));
one[0]=-1; one[1]=-1; two[0]=-1; two[1]=-1;
for(i=0; i<n-1; i++){ //n-1条边，无重边
scanf("%d %d", &a, &b);
a--; b--;
g[a][b]++; g[b][a]++;
g[a][n]++; g[b][n]++;
}
Top(n,0);
memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++)
adj[i].clear();
build(one[0],n);
hash1=dfs(one[0]);
memset(g, 0, sizeof(g));
for(i=0; i<n-1; i++){
scanf("%d %d", &a, &b);
a--; b--;
g[a][b]++; g[b][a]++;
g[a][n]++; g[b][n]++;
}
Top(n,1);
memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++)
adj[i].clear();
build(one[1],n);
hash2=dfs(one[1]);
if(hash1!=hash2 && two[1]!=-1){
memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++)
adj[i].clear();
build(two[1],n);
hash2=dfs(two[1]);
}
// printf("%d %d %d %d\n", one[0], two[0], one[1], two[1]);
printf("%s\n", hash1==hash2?"same":"different");
}
return 0;
}