# 28 条题解

• @ 2017-10-03 00:54:28
``````#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;
}
``````
• @ 2018-07-22 17:05:19
• @ 2017-08-27 11:53:50

//哈希大法好

``````#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];

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;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
*/

``````
• @ 2018-07-22 17:05:02

• @ 2017-04-08 19:45:19
``````/*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");
}

}

``````
• @ 2009-11-01 00:14:40

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)+'+'..即可

• @ 2009-10-29 13:57:05

标程都编译不过？

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

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

• @ 2016-11-17 14:27:38

最小表示法什么鬼。。。搜题解发现括号序列暴力。。
#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("");
}
}

• @ 2016-08-20 20:03:35
• @ 2016-05-20 18:57:02

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

• @ 2010-04-16 19:36:00

80分的同学看这里

每次xor后也要mod q

• @ 2009-11-07 18:25:42

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

• @ 2009-10-30 21:47:55

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

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

• @ 2009-10-30 12:49:02

水题,用哈西函数就行了

• @ 2009-10-30 07:38:47

占位

• @ 2009-10-29 20:31:27

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

• @ 2009-10-29 19:48:24

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

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

囧~ = =

• @ 2009-10-29 17:28:41

最小表示

• @ 2009-10-29 20:33:16

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

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

• @ 2009-10-29 14:27:53

前排啊！！！！

ID
1683

6

(无)

593

140

24%

4