Bean Language
Description
In the year 2099, the people in Earth established diplomatic relations between aliens from Pegasus galaxy. The Pegasusan people developed a kind of language called Bean Language, the words of which are based on graphic symbols. In ancient times of Pegasus, the Pegasusan had no paper to write on.
So, they carved every word on one rigid bean, and they string these beans to form a sentence.
Every graph symbol on bean consists of a certain number of spots and edges connect between these spots. The number of edges is exactly the number of spots minus 1, but all the spots are connected. Two Beans have the same spots and edges relations are considered to be the same word.
However, after the Pegasusan invented paper, the word of Bean Language differentiated into various handwritings. But handwritings of the same word have the same spots and edges relations. Like the two graphics in the fellow figure, they are the same word carved on bean and written on paper. Pegasusian can recognize the two forms are identical in no time, because they are so familiar with their own language.
Now, the Pegasusan provide us a dictionary of their words. The problem is that the people on Earth cannot identify the Bean Language words handwritings in one sight, especially when the word is more complex. So, that is your job to recognize the given two symbols are the same word or not.
Input
The first line of input is an integer number, which is the number of cases, k. The following 3k lines contain k case.
In each case, the first line is an integer n, which is the number of spots of a bean word (2 <= n <= 1000). The second line is the connect relation of the word in Bean Language dictionary, and the third line is the connect relation of a word in handwriting.
Because all the spots in each word are labeled as 1, 2, ..., n, the connect relation is a list as u1, v1, u2, v2, ..., un-1, vn-1. ui and vi denotes the two endpoints of one edge without direction, and the edges have no order.
For example the connect relation of the word in the figure above is 1 2 3 1 4 3 3 5 and 1 2 3 5 1 3 1 4. They are in fact the same word.
Output
For each case, output “same” if the two words are the same Bean Language word, else output “different”.
Sample Input
2
5
1 2 3 1 4 3 3 5
1 2 3 5 1 3 1 4
4
1 2 2 3 2 4
2 1 2 3 3 4
Sample Output
same
different
题意：树同构，
对于有根树，从根结点dfs找出每个结点的深度以及孩子个数（是它的所有孩子个数）存于数组，最后按深度优先升序，否就按孩子数
升序排列，最后把两棵树的深度-孩子个数的数组匹配，完全一样则同构。
对于无根树，求每个点的度数，每次把度数为1的点删去，最后只剩一个结点或两个结点。对与第一颗树，只求出一个结点，
然后对第二颗树，如果有两个结点就枚举这两个结点。之后直接按有根数的判定方法。
代码：
#include <stdio.h>
#include <stdlib.h>
#define maxn 1010
int in1[maxn], in2[maxn], th, son1[maxn], son2[maxn], p1, p2;
struct T
{
int u, v, next;
}m1[maxn * 2], m2[maxn * 2];
struct N
{
int dep, sn;
}dfn1[maxn], dfn2[maxn];
int cmp(const void* a,const void* b)
{
N* p=(N*)a;
N* q=(N*)b;
if(p->dep==q->dep) return p->sn-q->sn;
else return p->dep-q->dep;
}
void set(int n)
{
int i, j;
for (i = 1; i <= n; i++)
{
in1[i] = in2[i] = 0;
son1[i] = son2[i] = -1;
}
}
int del(int n, int * in, int * son, struct T * mm)
{
int s = 0, t = 0, q[maxn], pre, k = n, i, u;
for (i = 1; i <= n; i++)
{
if (in[i] == 1)
{
q[t++] = i;
}
}
pre = t;
while (s<t)
{
while (s < pre)
{
u = q[s++];
for (i = son[u]; i != -1; i = mm[i].next)
{
if (in[mm[i].v] != 0)
{
in[mm[i].v]--;
if (in[mm[i].v] == 1)
{
q[t++] = mm[i].v;
}
in[u] = 0;
break;
}
}
k--;
}
pre = t;
if (k == 1)
{
p1 = q[s];
return 1;
}
else if (k == 2)
{
p1 = q[s], p2 = q[s+1];
return 2;
}
}
}
int dfs(struct T * mm, struct N * dfn, int * son, int u, int f, int &k, int dep)
{
int i, j = k;
dfn[j].sn = 0;
dfn[j].dep = dep;
for (i = son[u]; i != -1; i = mm[i].next)
{
if (mm[i].v != f)
{
k++;
int num = dfs(mm, dfn, son, mm[i].v, u, k, dep + 1);
dfn[j].sn += num + 1;
}
}
return dfn[j].sn;
}
int com(int n, struct N * a, struct N * b)
{
int i;
for (i = 1; i < n; i++)
{
if (a[i].dep != b[i].dep || a[i].sn != b[i].sn)
{
return 0;
}
}
return 1;
}
int main()
{
int t, n, i, a1, a2, a3, u, v, h;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
set(n);
for (i = 1, th = 0; i < n; i++)
{
scanf("%d%d", &u, &v);
in1[u]++, in1[v]++;
m1[th].u = u, m1[th].v = v, m1[th].next = son1[u], son1[u] = th++;
m1[th].u = v, m1[th].v = u, m1[th].next = son1[v], son1[v] = th++;
}
del(n, in1, son1, m1);
a1 = p1;
for (i = 1, th = 0; i < n; i++)
{
scanf("%d%d", &u, &v);
in2[u]++, in2[v]++;
m2[th].u = u, m2[th].v = v, m2[th].next = son2[u], son2[u] = th++;
m2[th].v = v, m2[th].v = u, m2[th].next = son2[v], son2[v] = th++;
}
int h = del(n, in2, son2, m2);
a2 = p1;
if (h == 2)
{
a3 = p2;
}
int kk = 0;
dfs(m1, dfn1, son1, a1, -1, kk, 1);
qsort(dfn1, kk + 1, sizeof (N), cmp);
kk = 0;
dfs(m2, dfn2, son2, a2, -1, kk, 1);
qsort(dfn2, kk + 1, sizeof (N), cmp);
if (com(n, dfn1, dfn2))
{
printf("same\n");
}
else if (h == 2)
{
kk = 0;
dfs(m2, dfn2, son2, a3, -1, kk, 1);
qsort(dfn2, kk + 1, sizeof (N), cmp);
if (com(n, dfn1, dfn2))
{
printf("same\n");
}
else
{
printf("different\n");
}
}
else
{
printf("different\n");
}
}
system("pause");
return 0;
}
/**//*
2
5
1 2 3 5 1 3 1 4
1 2 3 1 4 3 3 5
2
5
1 2 3 1 4 3 3 5
1 2 3 5 1 3 1 4
*/