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
*/