先討論有根樹(shù)的同構(gòu)：
試圖確定兩顆樹(shù)的最小表示，如果最小表示相同則同構(gòu)。
明確一下樹(shù)的大小判斷標(biāo)準(zhǔn)：
① 根節(jié)點(diǎn)度數(shù)大的樹(shù)大
② 根節(jié)點(diǎn)度數(shù)一樣時(shí)，將子樹(shù)排序，然后依次判斷每個(gè)子樹(shù)，第一個(gè)子樹(shù)大的樹(shù)大
復(fù)雜度分析：
時(shí)間：排序均用快排，compare的復(fù)雜度是O(n)，快速排序進(jìn)行nlogn次compare，排序的復(fù)雜度是O(n2logn)更新link的復(fù)雜度為O(n2logn)，計(jì)算rank的復(fù)雜度為O(n2)，總的時(shí)間復(fù)雜度是O(n2logn)（上述考慮的是最壞情況，實(shí)際情況原小于理論值）
有根樹(shù)的同構(gòu)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); //讀入一個(gè)01字符串，0代表遠(yuǎn)離根節(jié)點(diǎn)，1代表靠近根節(jié)點(diǎn)
rebuild(s);
hash1=dfs(0);
scanf("%s",s);
rebuild(s);
hash2=dfs(0);
printf("%s\n", hash1==hash2?"same":"different");
}
return 0;
}
對(duì)于無(wú)根樹(shù)，只要確定一個(gè)根，就轉(zhuǎn)換成有根樹(shù)同構(gòu)的判斷了
將樹(shù)看成無(wú)向圖，進(jìn)行拓?fù)渑判?每次刪除度為1的點(diǎn))，最后剩余1或2個(gè)點(diǎn)。
如果是1個(gè)點(diǎn)，以該點(diǎn)為根建立有根樹(shù)
如果是2個(gè)點(diǎn)，一棵樹(shù)以任一點(diǎn)為根建樹(shù)，另一棵樹(shù)分別以2個(gè)點(diǎn)建立樹(shù)，判斷兩次。
2009合肥賽區(qū)網(wǎng)絡(luò)預(yù)賽 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; //節(jié)點(diǎn)數(shù)
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) //拓?fù)渑判蛘腋?/span>
{
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個(gè)節(jié)點(diǎ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條邊，無(wú)重邊
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;
}