#include <bits/stdc++.h>
using namespace std;

const int maxn = 55;
int k, n, deg[maxn];
vector<int> G[maxn];
map<string, set<int> > res;
set<set<int> > ans;

string dfs(int u) {
    if (G[u].empty()) {
        return "()";
    }
    string tmp[maxn];
    for (size_t i = 0; i < G[u].size(); i++) {
        tmp[i] = dfs(G[u][i]);
    }
    sort(tmp, tmp + G[u].size());
    string ans = "(";
    for (size_t i = 0; i < G[u].size(); i++) {
        ans += tmp[i];
    }
    ans += ")";
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> k >> n;
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            G[j].clear();
            deg[j] = 0;
        }
        for (int j = 1; j < n; j++) {
            int u, v;
            cin >> u >> v;
            deg[v]++;
            G[u].push_back(v);
        }
        for (int j = 1; j <= n; j++) {
            if (deg[j] == 0) {
                res[dfs(j)].insert(i);
                break;
            }
        }
    }
    for (auto it : res) {
        ans.insert(it.second);
    }
    for (auto it : ans) {
        cout << *it.begin();
        for (auto x = ++it.begin(); x != it.end(); x++) {
            cout << "=" << *x;
        }
        cout << endl;
    }
    return 0;
}

题解

//哈希大法好

#include<bits/stdc++.h>
#define N 100005
#define LL long long
#define bs1 2333
#define bs2 2237
#define mod1 1000000007
#define mod2 1000000009
#define pr pair<LL,LL>
using namespace std;

struct edge{
    int ed,nxt;
}e[N<<1];

int n,m,q,tp,rt,mxd,fst[N],in[N],sz[N],vis[N];
LL hsh1[N],hsh2[N],tmp1[N],tmp2[N];
map<pr,int> mp;
vector<int> p[N];

void inline link(int x,int y){
    e[++tp]=(edge){y,fst[x]},fst[x]=tp,in[y]++;
}

void inline dfs(int x,int d){
    LL wxh1=bs2,wxh2=bs1,num=0;
    sz[x]=1,mxd=max(mxd,d); 
    for(int i=fst[x],u;i;i=e[i].nxt){
        dfs(u=e[i].ed,d+1),num++,hsh1[x]^=hsh1[u],hsh2[x]^=hsh2[u];
        (wxh1+=tmp1[sz[u]])%=mod1,(wxh2+=tmp2[sz[u]])%=mod2,sz[x]+=sz[u];
    }
    (hsh1[x]+=tmp1[sz[x]])%=mod1,(hsh2[x]+=tmp2[sz[x]])%=mod2;
    (hsh1[x]^=wxh1)%=mod1,(hsh2[x]^=wxh2)%=mod2;
    (hsh1[x]*=num)%=mod1,(hsh2[x]*=num)%=mod2;
}

pr inline solve(){
    tp=mxd=0;
    for(int i=1;i<=m;i++) fst[i]=in[i]=hsh1[i]=hsh2[i]=0;
    for(int i=1,x,y;i<m;i++) scanf("%d%d",&x,&y),link(x,y);
    for(int i=1;i<=m;i++) if(!in[i]) rt=i;
    dfs(rt,1);
    return make_pair(hsh1[rt],hsh2[rt]);
}

int main(){
//  freopen("B.in","r",stdin);
    scanf("%d%d",&n,&m),tmp1[0]=tmp2[0]=1;
    for(int i=1;i<=m;i++) 
        tmp1[i]=tmp1[i-1]*bs1%mod1,tmp2[i]=tmp2[i-1]*bs2%mod2;
    for(int i=1;i<=n;i++){
        pr tmp=solve();
        if(mp[tmp]) p[mp[tmp]].push_back(i); 
        else vis[mp[tmp]=i]=1;
    }
    for(int i=1;i<=n;i++)
        if(vis[i]){
            printf("%d",i);
            for(int j=0;j<p[i].size();j++) printf("=%d",p[i][j]);
            puts("");
        }
}
/*
3 7 
7 2 7 1 7 6 2 3 1 4 6 5
7 2 7 1 2 3 1 4 1 5 5 6
4 3 3 2 4 1 1 7 5 6 4 5
*/

/*http://m.blog.csdn.net/article/details?id=51994966
把树的拓扑结构表示成一个由括号组成字符串。
*/
#include <map>
#include <string>
#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 55 
using namespace std;
map <string, set<int> > Map;
set <set <int> > ans;


int degree[maxn];
vector <int> Next[maxn];

const string leave = "()";
string build(int pos)
{
    if (Next[pos].empty()) return leave;
    int sn = Next[pos].size();
    string* sub = new string[sn];
    for (int i = 0; i < sn; i++)
        sub[i] = build(Next[pos][i]);
    sort(sub,sub+sn);
    string res = "(";
    for (int i = 0; i < sn; i++) res += sub[i];
    res += ")";
    delete []sub;
    return res;
}

int main()
{
    int k,n;
    scanf("%d%d",&k,&n);
    for (int ti = 1;ti <=k;ti++)
    {
        for (int i = 1; i <=n; i++)
        {
            degree[i] = 0;
            Next[i].clear();
        }
        for (int i = 1; i <= n - 1; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            degree[y]++;
            Next[x].push_back(y);
        }
        int root = 0;
        for (int i = 1; i <=n; i++)
            if (degree[i] == 0)
            {
                root = i;
                break;
            }
        string eigenstring = build(root);
        Map[eigenstring].insert(ti);
    }
    map <string, set<int> >::iterator it = Map.begin();
    for (; it !=Map.end(); it++)
    {
        ans.insert(it->second);
    }
    
    set <set <int> >::iterator i = ans.begin();
    for (; i != ans.end();i++)
    {
        set<int>::iterator j = i->begin();
        printf("%d",*j);
        j++;
        for (;j!=i->end();j++)
        {
            printf("=%d",*j);
        }
        printf("\n");
    }
    
}

hash

跟树的做法一样

显然子树同构，所以如果所有子树可以存在一种映射使得子树同构，则原树同构。

令h(i)为第I个儿子对应的HASH值，先将h排序，然后则有一种不错的HASH函数：

hash(v)=a*p xor hash(1) mod p*p xor hash(2)*p xor hash(3) mod p...*b mod p

换句话说，就是从某个常数开始，每次乘以p，和一个元素异或，再除以q取余，再乘以p，和下一个元素异或，除以q取余……一直进行到最后一个元素为止。最后把所得到的结果乘以b，再对q取余。

注意最后的B是要乘的，考虑线性。

最后直接判断答案即可。

对楼下的楼下：儿子之间的先后顺序不影响树的同构..貌似反例很好找

另外实际上，可以构造一个hash令不同构的完全不等：

令h(i)为第I个儿子对应的HASH值，先将h排序，然后h(v)=h(1)+'+'+h(2)+'+'..即可

标程都编译不过？

car－ P1683 CPP Evolution SmdCn 2009-10-29 13:38:10

car－ P1683 FPC Evolution SmdCn 2009-10-29 13:37:47

最小表示法什么鬼。。。搜题解发现括号序列暴力。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>

using namespace std;
vector<int>v[200];
int vis[200];
string ans[200];
int k,n;

string dfs(int x){
string t[100];
for(int i=0;i<v[x].size();i++){
t[i]=dfs(v[x][i]);
}
sort(t,t+v[x].size());
string ret="";
for(int i=0;i<v[x].size();i++)
ret+=t[i];
return "("+ret+")";
}

int main(){
scanf("%d%d",&k,&n);
for(int i=1;i<=k;i++){
memset(vis,0,sizeof(vis));
for(int i=0;i<200;i++)v[i].clear();
for(int j=1;j<n;j++){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
vis[y]=1;
}
for(int j=1;j<=n;j++)if(!vis[j]){ans[i]=dfs(j);break;}
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=k;i++){
if(vis[i])continue;
printf("%d",i);
for(int j=i+1;j<=k;j++){
if(ans[i]==ans[j]){
printf("=%d",j);
vis[j]=1;
}
}
puts("");
}
}

题解+代码
题解+代码

字典序。。。字典序。。。本以为是表示成**字符串**后的字典序，WA6次好心酸。
hash不会用，将树完全括号化就好，子树按字典序快排。

80分的同学看这里

每次xor后也要mod q

用括号序列，把子树的儿子节点的子括号序列按一定方式排序后连接起来，再在两边加上括号就为该子树的括号序列。。。只需要判断序列是否相等就行了。。膜拜hyf神牛。。。在他的点播下一次AC。。

我不太清楚这样对不对，希望大牛能找个反例：

先求根结点，然后不考虑原来结点编号，多叉转二叉，按前序遍历给每个结点赋值1，2，3...n，然后求中序后序，如果都相同这2棵树就是同构的。

水题,用哈西函数就行了

占位

Orz求低于O(n^5)的同构算法

NWERC上AC的程序，到了PKU就WA了~

PKU上AC的程序，到了vijos上就WA了~

囧~ = =

最小表示

可以考察每个节点的度数就判断两个树是否同构么...

一点都不会也....求讲解- -..

前排啊！！！！