|
题目大意：给两个字符串序列，序列中的字符为0或1，表示从一个中心点出发，0表示远离中心点，1表示接近中心点，求这两个序列表示的图是否是相同的
解题思路：就是求形成的树是否是相同的。通过字符串序列建立两颗树，把树的节点按照深度和儿子节点数排好序后，再来判断每个节点的深度和儿子节点数是否相等，相等则说明是同构树，否则是异构树。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int depth;
int son;
bool operator < (const node &tmp) const
{
if(depth == tmp.depth)
return son < tmp.son;
return depth < tmp.depth;
}
};
const int maxn = 3010;
int t;
int createTree(char *str, node *tree);
int main()
{
char str1[maxn], str2[maxn];
node tree1[maxn], tree2[maxn];
scanf("%d", &t);
while(t-- != 0)
{
scanf("%s", str1);
scanf("%s", str2);
int num1 = createTree(str1, tree1);
int num2 = createTree(str2, tree2);
if(num1 != num2)
{
printf("different\n");
continue;
}
else
{
int k;
for(k = 0; k < num1; k++)
{
if(tree1[k].depth != tree2[k].depth || tree1[k].son != tree2[k].son)
{
printf("different\n");
break;
}
}
if(k == num1)
printf("same\n");
}
}
return 0;
}
int createTree(char *str, node *tree)
{
int len = strlen(str);
int parent[maxn];
int index = 1, t = 0;
parent[0] = tree[0].depth = tree[0].son = 0;
for(int i = 0; str[i] != '\0'; i++)
{
if(str[i] == '0')
{
parent[index] = t;
tree[index].depth = tree[t].depth + 1;
tree[index].son = 0;
t = index++;
}
else
{
tree[parent[t]].son += tree[t].son + 1;
t = parent[t];
}
}
sort(tree, tree + index);
return index;
}
| 
转播
