Warning: session_start(): open(/tmp/sess_dfcc1c1bd7df9ffe3057cde9eb9f3e90, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:树同构 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:树同构

树同构

无根树同构

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

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

树哈希

算法简介

利用哈希 $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 sz2[MAXN],mson[MAXN],tot_sz,root_sz;
void find_root(int u,int fa){
	sz2[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);
		sz2[u]+=sz2[v];
		mson[u]=max(mson[u],sz2[v]);
	}
	mson[u]=max(mson[u],tot_sz-sz2[u]);
	if(mson[u]<root_sz)
	root_sz=mson[u];
}
int sz[MAXN],h1[MAXN],h2[MAXN];
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;
}
vector<pair<int,int> >root[MAXN];
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);
			}
		}
		tot_sz=root_sz=n;
		find_root(1,0);
		_rep(i,1,n){
			if(mson[i]==root_sz){
				Hash(i,0);
				root[k].push_back(make_pair(h1[i],h2[i]));
			}
		}
		_rep(i,1,k){
			if(cmp(i,k)){
				enter(i);
				break;
			}
		}
	}
	return 0;
}

最小表示法

算法练习

2020-2021/teams/legal_string/jxm2001/树同构.1597416684.txt.gz · 最后更改: 2020/08/14 22:51 由 jxm2001