先討論有根樹的同構：
試圖確定兩顆樹的最小表示，如果最小表示相同則同構。
明確一下樹的大小判斷標準：
① 根節點度數大的樹大
② 根節點度數一樣時，將子樹排序，然后依次判斷每個子樹，第一個子樹大的樹大
復雜度分析：
時間：排序均用快排，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;
}