树同构

无根树同构

对每棵树，至多只有两个重心。显然两棵无根树同构等价于以两个无根树的某个重心为根的两个有根树同构。

于是无根树同构问题可以转化为有根树同构问题，故下面只考虑有根树同构问题。

树哈希

算法简介

利用哈希 $O(n)$ 时间判断树同构，不能保证完全正确。

算法思想

构造各种哈希函数，当所有哈希值相同时才认为同构，下面给出两种哈希函数。

$$h_{1,u}=\text{sz}_u+\sum_{v\in \text{son}(u)}\text{sz}_vh_{1,v}$$

$$h_{2,u}=\text{sz}_u+\text{sz}_u\sum_{v\in \text{son}(u)}\text{sz}_vh_{2,v}$$

如果需要更高准确率，可以考虑构造 $f\{1,2\cdots n\}\to \{p_1,p_2\cdots p_n\}$，并将上式 $\text{sz}_u$ 替换为 $p_{\text{sz}_u}$，其中 $p$ 序列可以为随机数表，素数表等等。

算法模板

洛谷p5043

查看代码

const int MAXN=55,Mod=1e9+7;
struct Edge{
	int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt]=Edge{v,head[u]};
	head[u]=edge_cnt;
}
int sz[MAXN],mson[MAXN],tot_sz,root_sz;
int h1[MAXN],h2[MAXN];
vector<int> rt;
vector<pair<int,int> >root[MAXN];
void find_root(int u,int fa){
	sz[u]=1;mson[u]=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)
		continue;
		find_root(v,u);
		sz[u]+=sz[v];
		mson[u]=max(mson[u],sz[v]);
	}
	mson[u]=max(mson[u],tot_sz-sz[u]);
	if(mson[u]<root_sz)
	root_sz=mson[u];
}
void Hash(int u,int fa){
	sz[u]=1,h1[u]=h2[u]=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		Hash(v,u);
		sz[u]+=sz[v];
		h1[u]=(h1[u]+1LL*h1[v]*sz[v])%Mod;
		h2[u]=(h2[u]+1LL*h2[v]*sz[v])%Mod;
	}
	h1[u]=(h1[u]+sz[u])%Mod;
	h2[u]=(1LL*h2[u]*sz[u]+sz[u])%Mod;
}
bool cmp(int a,int b){
	if(root[a].size()!=root[b].size())
	return false;
	if(root[a].size()==1){
		if(root[a][0]==root[b][0])
		return true;
	}
	else{
		if(root[a][0]==root[b][0]&&root[a][1]==root[b][1])
		return true;
		if(root[a][0]==root[b][1]&&root[a][1]==root[b][0])
		return true;
	}
	return false;
}
int main()
{
	int T=read_int(),n,p;
	_rep(k,1,T){
		n=read_int(),edge_cnt=0;
		_rep(i,1,n)head[i]=0;
		_rep(i,1,n){
			p=read_int();
			if(p)Insert(p,i),Insert(i,p);
		}
		rt.clear();
		tot_sz=root_sz=n;
		find_root(1,0);
		_rep(i,1,n){
			if(mson[i]==root_sz)
			rt.push_back(i);
		}
		_for(i,0,rt.size()){
			Hash(rt[i],0);
			root[k].push_back(make_pair(h1[rt[i]],h2[rt[i]]));
		}
		_rep(i,1,k){
			if(cmp(i,k)){
				enter(i);
				break;
			}
		}
	}
	return 0;
}

最小表示法

算法简介

利用每棵树的最小字典序的括号序列判断树同构。

算法思想

易知两棵树同构等价于两棵树最小字典序的括号序列相同。当然实现的时候不需要真正模拟括号序列，可以考虑使用 $01$ 串。

于是考虑如何快速求出每棵树的最小表示法。

一个比较暴力的算法是先求出所有子树的最小表示法，然后用 $\text{Trie}$ 树实现 $O(n)$ 排序，然后顺次拼接，最后最外层添加括号。

上述算法的时间复杂度为 $O(n^2)$，考虑优化算法。

发现可以用名次代替括号序列。考虑根据深度化为树，每个深度为 $d$ 的结点的名次序列由深度为 $d+1$ 的结点的名次构成。

注意名次是指在两棵树中所有深度为 $d+1$ 的结点中的名次，初始叶子结点名次均为 $0$。

然后对所有深度为 $d$ 的结点的名次序列再次排序，如果使用基数排序，可以使得总时间复杂度为 $O(n)$。

CVBB ACM Team

目录

树同构

无根树同构

树哈希

算法简介

算法思想

算法模板

最小表示法

算法简介

算法思想

算法练习

CVBB ACM Team

用户工具

站点工具

目录

树同构

无根树同构

树哈希

算法简介

算法思想

算法模板

最小表示法

算法简介

算法思想

算法练习

页面工具