题目描述
一些主要城市拥有树形的地铁系统,即在任何一对车站之间,有且只有一种方式可以乘坐地铁。
此外,这些城市大多数都有一个中央车站。
想象一下,你是一名在拥有树形地铁系统的城市游玩的游客,你想探索该城市完整的地铁线路。
你从中央车站出发,随机选择一条地铁线,然后乘坐地铁行进。
每次到达一个车站,你都将选择一条尚未乘坐过的地铁线路进行乘坐。
如果不存在未乘坐过的线路,则退回到上一个车站,再做选择。
直到你将所有地铁线路都乘坐过两次(往返各一次),此时你将回到中央车站。
之后,你以一种特殊的方式回忆自己的坐车过程,你将你的完整地铁乘坐路线编码为一个二进制字符串。
其中0编码表示你乘坐地铁线路到达距离中央车站更远的一站,1编码表示你乘坐地铁线路到达距离中央车站更近的一站。
样例
输入样例:
2
0010011101001011
0100011011001011
0100101100100111
0011000111010101
输出样例:
same
different
算法1
(dfs递归)
性质:如果两颗树是同构的,当且仅当 这两颗树的最小表示是相同的。
可以这样理解。
可以对树的每个子树,都进行字典序的排序,逐层递归。
最后如果两棵树同构的话,那么只有可能是排列上的不同,即可以通过最小表示,对每棵树生成唯一的最小表示。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int T;
string dfs(string &seq, int &u){
u ++;
vector<string> seqs;
while (seq[u] == '0') seqs.push_back(dfs(seq, u));
u ++;//当str[u] == 1的时候需要抛弃回去的那条边,所以u ++;
sort(seqs.begin(), seqs.end());
string res = "0";
for (auto &s : seqs) res += s;
res += '1';//因为每次回去抛弃了那条边,所以得补上,上面的1
return res;
}
int main(){
cin >> T;
while (T --){
string a, b;
cin >> a >> b;
a = '0' + a + '1';
b = '0' + b + '1';
int ua = 0, ub = 0;
auto ra = dfs(a, ua), rb = dfs(b, ub);
if (ra != rb) puts("different");
else puts("same");
}
return 0;
}