江门建站网站模板,2023免费网站推广大全,建立音乐网站,wordpress 安装字体树的同构problemsolutioncodesolutioncodeproblem
模板题
solution
Ⅰ. 最小表示法
将树转化为 0/10/10/1 括号序列#xff1a;从根开始 dfs\text{dfs}dfs#xff0c;000 就往下遍历一个儿子#xff0c;111 就返回#xff0c;构成一个 2n2\times n2n 的括号序列。
显然…
树的同构problemsolutioncodesolutioncodeproblem
模板题
solution
Ⅰ. 最小表示法
将树转化为 0/10/10/1 括号序列从根开始 dfs\text{dfs}dfs000 就往下遍历一个儿子111 就返回构成一个 2×n2\times n2×n 的括号序列。
显然括号序列与树的形态是唯一对应的。
有根树 若儿子遍历顺序是固定的。显然括号序列只有唯一一种。若儿子遍历顺序不固定。就会有多种合法的括号序列不妨钦定字典序最小的为这棵树的括号序列这个特殊的括号序列有单独的名称最小表示。
显然两棵有根树的最小表示相同是同构的充要条件。
具体实现递归地构造对于点 uuu先把儿子 vvv 的括号序列都处理出来后按照儿子的字典序从小到大排序然后顺次接起来。在这个拼接的括号序列外面用 000进入 uuu 子树求解111完成 uuu 子树内的遍历 “包起来”就表示把 uuu 子树遍历完然后返回上一层的最小表示了。
时间复杂度为 O(n2)O(n^2)O(n2)。最坏情况为链。
因为括号序列肯定是用字符串 string\text{string}string 类型储存。
那么 f[u]f[v]f[u]f[v]f[u]f[v] 这一句话的操作复杂度其实是 O(len)O(len)O(len) 的。
无根树
比较暴力的想法就是对于每个点都当作根做一遍 dfs\text{dfs}dfs。时间复杂度为 O(n3)O(n^3)O(n3)。
对于本题而言又有 mmm 棵树时间复杂度就是 O(n3m)O(n^3m)O(n3m) 的。
实际上最小表示法就是为了定义一个规则让一棵树拥有唯一的括号序列。如果喜欢最大表示法也是可以的。
所以可以对无根树找一个特殊的规则来区别不同构的树。
这里我们选择重心为根时的括号序列当作无根树的括号序列代表。
两个重心的话就取字典序较小的。
时间复杂度就降为 O(n2m)O(n^2m)O(n2m)。
code
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
#define maxn 55
int n, m, Max, cnt;
string Min;
struct node { int to, nxt; }E[maxn 1];
int head[maxn], siz[maxn], MaxSiz[maxn];
string f[maxn], g[maxn], mp[maxn];void init() {memset( head, -1, sizeof( head ) );memset( MaxSiz, 0, sizeof( MaxSiz ) );cnt 0; Max n; Min 1;
}void addedge( int u, int v ) {E[cnt] { v, head[u] };head[u] cnt ;
}void dfs1( int u, int fa ) {siz[u] 1;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( v fa ) continue;dfs1( v, u );siz[u] siz[v];MaxSiz[u] max( MaxSiz[u], siz[v] );}MaxSiz[u] max( MaxSiz[u], n - siz[u] );Max min( Max, MaxSiz[u] );
}void dfs2( int u, int fa ) {f[u] 0;for( int i head[u];~ i;i E[i].nxt )if( E[i].to ^ fa ) dfs2( E[i].to, u );int tot 0;for( int i head[u];~ i;i E[i].nxt )if( E[i].to ^ fa ) g[ tot] f[E[i].to];sort( g 1, g tot 1 );for( int i 1;i tot;i ) f[u] g[i];f[u] 1;
}int main() {scanf( %d, m );for( int j 1;j m;j ) {scanf( %d, n );init();for( int i 1, x;i n;i ) {scanf( %d, x );if( x ) addedge( x, i ), addedge( i, x );}dfs1( 1, 0 );for( int i 1;i n;i )if( MaxSiz[i] Max ) {dfs2( i, 0 );Min min( Min, f[i] );}mp[j] Min;for( int i 1;i j;i )if( mp[i] mp[j] ) {printf( %d\n, i );break;}}return 0;
}solution
Ⅱ . 树哈希
多项式哈希即 [1,r][1,r][1,r] 的哈希值减去 r−l1r-l1r−l1 乘上 [1,l][1,l][1,l] 的哈希值。
同理有根树且儿子有顺序哈希就是一一对应正确的。
如果有根树且儿子没顺序就按照儿子的哈希值排序后再哈希。
有根树扩展到无根树也是寻找重心。
得出哈希值后暴力比较即可。
时间复杂度为 O(nmlogn)O(nm\log n)O(nmlogn)瓶颈在于排序。如果你不喜欢 log\loglog基排就行
其实树哈希就是没有最小表示法的字符串相关操作带来的巨大复杂度而已。
哈希唯一的缺点就是会冲突不能保证一定稳定但也不至于很容易就被卡掉。
code
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
#define int long long
#define mod 1019260817
#define base 19491001
#define maxn 55
struct node { int to, nxt; }E[maxn 1];
pair int, int f[maxn], g[maxn];
int Pow[maxn], Hash[maxn], head[maxn], siz[maxn], MaxSiz[maxn], dep[maxn];
int n, m, cnt, rt1, rt2, Max;void addedge( int u, int v ) {E[cnt] { v, head[u] };head[u] cnt ;
}void dfs1( int u, int fa ) {siz[u] 1;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( v fa ) continue;dfs1( v, u );siz[u] siz[v];MaxSiz[u] max( MaxSiz[u], siz[v] );}MaxSiz[u] max( MaxSiz[u], n - siz[u] );if( MaxSiz[u] Max ) Max MaxSiz[u], rt1 u, rt2 0;else if( MaxSiz[u] Max ) rt2 u;
}void dfs2( int u, int fa ) {Hash[u] Pow[siz[u] 1] * dep[u] % mod;for( int i head[u];~ i;i E[i].nxt ) if( E[i].to ^ fa ) dep[E[i].to] dep[u] 1, dfs2( E[i].to, u );int tot 0;for( int i head[u];~ i;i E[i].nxt )if( E[i].to ^ fa ) g[ tot] { Hash[E[i].to], siz[E[i].to] };sort( g 1, g tot 1 );for( int i 1;i tot;i )Hash[u] ( Hash[u] g[i].first * Pow[siz[u]] ) % mod, siz[u] g[i].second;
}signed main() {Pow[0] 1;for( int i 1;i maxn;i ) Pow[i] Pow[i - 1] * base % mod;scanf( %lld, m );for( int k 1;k m;k ) {memset( MaxSiz, 0, sizeof( MaxSiz ) );memset( head, -1, sizeof( head ) );cnt 0; Max mod;scanf( %lld, n );for( int i 1, x;i n;i ) {scanf( %lld, x );if( x ) addedge( i, x ), addedge( x, i );}dfs1( 1, 0 );dep[rt1] 1;dfs2( rt1, 0 );f[k].first Hash[rt1];if( ! rt2 ) goto pass;dep[rt2] 1;dfs2( rt2, 0 );f[k].second Hash[rt2];if( f[k].first f[k].second ) swap( f[k].first, f[k].second );pass : ; }for( int i 1;i m;i )for( int j 1;j i;j )if( f[i] f[j] ) { printf( %lld\n, j ); break; }return 0;
}
