lsw1's blog

By lsw1, history, 6 weeks ago, In English

theres a problem need to see whether some trees look like tihs:

for two trees T1 and T2,if it is able to relabel the 2 trees vertexs so that the two trees look exactly the same,then those two trees are isomorphism(i dont know if this is right to call it).then need to divide these trees into the least number groups so that all the trees in each group are isomorphism.

its obvious that this problem need to be solved by tree hash.my two tree hash function look like this:

$$$f1_{now}=\bigoplus f1_{son(now,i)}\times seed+size_{son(now,i)},f2_{now}=1+\sum f_{son(now,i)}\times prime(size_{son(now,i)})$$$

make every vertexs in one tree a root,and tree-DP the tree.that get a answer.sort these answer.obviously,if two trees are isomorphism,then these answer must be same.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 114514;
const int MAXN = 50;
const int MAXM = 1e3;
bool prime[MAXM + 5];
vector<int>ans;
void sieve()
{
	for(int i = 2;i <= MAXM;i++)
	{
		prime[i] = true;
	}
	for(int i = 2;i <= MAXM;i++)
	{
		if(prime[i])
		{
			ans.push_back(i);
		}
		for(int j = 0;j < ans.size() && i * ans[j] <= MAXM;j++)
		{
			prime[i * ans[j]] = false;
			if(i % ans[j] == 0)
			{
				break;
			}
		}
	}
}
int n[MAXN + 5];
vector<int>graph[MAXN + 5][MAXN + 5];
long long f[3][MAXN + 5][MAXN + 5],hsh1[MAXN + 5][MAXN + 5],hsh2[MAXN + 5][MAXN + 5];
int sz[MAXN + 5][MAXN + 5];
void dfs(int t,int u,int fa)
{
	sz[t][u] = 1;
	for(int i = 0;i < graph[t][u].size();i++)
	{
		int v = graph[t][u][i];
		if(v == fa)
		{
			continue;
		}
		dfs(t,v,u);
		sz[t][u] += sz[t][v];
	}
}
void dfs1(int t,int u,int fa)
{
	f[1][t][u] = 0;
	long long sum = 0;
	for(int i = 0;i < graph[t][u].size();i++)
	{
		int v = graph[t][u][i];
		if(v == fa)
		{
			continue;
		}
		dfs1(t,v,u);
		f[1][t][u] ^= f[1][t][v];
		sum += sz[t][v];
	}
	f[1][t][u] = f[1][t][u] * MOD + sum;
}
void dfs2(int t,int u,int fa)
{
	f[2][t][u] = 1;
	for(int i = 0;i < graph[t][u].size();i++)
	{
		int v = graph[t][u][i];
		if(v == fa)
		{
			continue;
		}
		dfs2(t,v,u);
		f[2][t][u] += f[2][t][v] * ans[sz[t][v] &mdash; 1];
	}
}
bool check(int x,int y)
{
	if(n[x] != n[y])
	{
		return false;
	}
	for(int i = 1;i <= n[x];i++)
	{
		if(hsh1[x][i] != hsh1[y][i] || hsh2[x][i] != hsh2[y][i])
		{
			return false;
		}
	}
	return true;
}
int main()
{
	sieve();
	int m;
	cin >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> n[i];
		for(int j = 1;j <= n[i];j++)
		{
			int x;
			cin >> x;
			if(x != 0)
			{
				graph[i][j].push_back(x);
				graph[i][x].push_back(j);
			}
		}
		dfs(i,1,0);
		for(int j = 1;j <= n[i];j++)
		{
			dfs1(i,j,0);
			hsh1[i][j] = f[1][i][j];
			dfs2(i,j,0);
			hsh2[i][j] = f[2][i][j];
		}
		sort(hsh1[i] + 1,hsh1[i] + n[i] + 1);
		sort(hsh2[i] + 1,hsh2[i] + n[i] + 1);
		for(int j = 1;j <= n[i];j++)
		{
			cout << hsh2[i][j] << " ";
		}
		cout << endl;
	}
	for(int i = 1;i <= m;i++)
	{
		bool flag = false;
		for(int j = 1;j < i;j++)
		{
			if(check(i,j))
			{
				flag = true;
				cout << j << endl;
				break;
			}
		}
		if(!flag)
		{
			cout << i << endl;
		}
	}
	return 0;
}

the input is:

4 
4 0 1 1 2 
4 2 0 2 3 
4 0 1 1 1 
4 0 1 2 3 

obviously,the tree 1,2,4 should go to onw group,and the tree 3 should goto another group.

but my programme say that 1 goto a group,2 and 4 goto a group,3 goto a group. the four trees hash look like these:

hash 1:
114517 114519 13113685228 13113914254
114520 458060 13113685227 52454168328
3 229032 229032 229032
114520 458060 13113685227 52454168328

hash 2:
12 24 67 71
17 43 51 124
7 36 36 36
17 43 51 124

so i think that the hash are ok,because two hash both give a certain same answer.

but anyway,what's wrong with my programme?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lsw1 (previous revision, new revision, compare).