\(\text{problem}\)

无根树同构的判断

\(\text{Analysis}\)

考虑树哈希，注意使用较正确的哈希方法

无根树同构有个性质

只要判断以这两棵树的重心为根是否同构即可

\(\text{Code}\)

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 105, INF = 0x3f3f3f3f, P = 998244353;

int m, n, rt, siz[N], h[N], son[N], hash[N], tot;

struct edge{

	int to, nxt;

}e[N];

inline void add(int x, int y)

{

	e[++tot] = edge{y, h[x]}, h[x] = tot;

}

void getrt(int x, int fa)

{

	siz[x] = 1, son[x] = 0;

	for(int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == fa) continue;

		getrt(v, x), siz[x] += siz[v];

		son[x] = max(son[x], siz[v]);

	}

	son[x] = max(son[x], n - siz[x]);

	rt = son[x] < son[rt] ? x : rt;

}

int hs[N][N], hv[N];

inline bool cmp(int x, int y){return hv[x] < hv[y];}

int dfs(int x, int fa)

{

	int res = 2021; hs[x][0] = 0, siz[x] = 1;

	for(int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == fa) continue;

		dfs(v, x), siz[x] += siz[v], hs[x][++hs[x][0]] = v;

	}

	sort(hs[x] + 1, hs[x] + hs[x][0] + 1, cmp);

	for(int i = 1; i <= hs[x][0]; i++) res = ((long long)hv[hs[x][i]] * siz[hs[x][i]] + res) % P;

	return hv[x] = res;

}

int main()

{

	scanf("%d", &m), son[0] = INF;

	for(int j = 1; j <= m; j++)

	{

		scanf("%d", &n);

		tot = 0, memset(h, 0, sizeof h);

		for(int i = 1, x; i <= n; i++)

		{

			scanf("%d", &x);

			if (x) add(x, i), add(i, x);

		}

		rt = 0, getrt(1, 0), hash[j] = dfs(rt, 0);

		for(int i = 1; i <= n; i++)

		if (i ^ rt && siz[i] == son[rt]) hash[j] = min(hash[j], dfs(i, 0));

		for(int i = 1; i <= j; i++)

		if (hash[i] == hash[j]){printf("%d\n", i); break;}

	}

}

巴特西

LG P5043 树同构

\(\text{problem}\)

\(\text{Analysis}\)

\(\text{Code}\)

最新文章

热门文章