- 题目大意: 给出一堆树,求同构(拓扑结构相同)树的集合
- 思路: 一开始写了个前序求置换序列,然后对比后序是否相等,但wa了,还需要对子树进行排序输出其dfs序,但是直接输出按节点多少排序的序列太复杂,于是将一个节点的dfs抽象成\(()\),于是对树\(1 -> 2 , 1 -> 3\)输出的dfs序为\((()())\)
#include<bits/stdc++.h>
#define ll long long
#define FOR(i,n) for(int i =1; i <= n;++i )
#define FOR0(i,n) for(int i =0; i < n;++i )
#define inf 0x3f3f3f3f
using namespace std; int k,n;
int vis[110];
struct node{vector<int> son;int idx;node(){idx = 0;}
};
struct Tree{int root = 0;node nodes[110];string pre;int in[110];int cur = 1;int idx;string getPre(int root){
// if(!root) return ;
// getPre(nodes[root].l);
// getPre(nodes[root].r);string z[110];int idx = 0;for(auto i:nodes[root].son){z[++idx] = getPre(i);}sort(z+1,z+1+idx);for(int i=2;i<=idx;++i){z[1] = z[1]+z[i];}return '('+z[1]+')';}bool operator == (Tree const tr)const{int len = pre.size();FOR0(i,len){if(pre[i] != tr.pre[i]) return false;}return true;}
};
vector<Tree> ve;
int main(){cin >> k >> n;FOR(i,k){
// cout << i << endl;Tree cTree;int fr,to;FOR(j,n-1){cin >> fr >> to;
// if(cTree.nodes[fr].l == 0){
// cTree.nodes[fr].l = to;
// }else{
// int bro = cTree.nodes[fr].l;
// while(cTree.nodes[bro].r){
// bro = cTree.nodes[bro].r;
// }
// cTree.nodes[bro].r = to;
// }cTree.nodes[fr].son.push_back(to);cTree.nodes[to].idx = 1;}FOR(j,n){if(cTree.nodes[j].idx==0){cTree.root =j;break;}}cTree.cur = 1;cTree.pre = cTree.getPre(cTree.root);
// cTree.cur = 1;
// cTree.getIn(cTree.root);cTree.idx = i;ve.push_back(cTree);}for(int i=0;i<k;++i){if(vis[i]) continue;vis[i] = 1;cout << ve[i].idx;for(int j=i+1;j<k;++j){ if(i==j || vis[j]) continue;if(ve[i]==ve[j]){cout << '=' << ve[j].idx;vis[j] = 1;}}cout << endl;}for(int i=0;i<k;++i){if(!vis[i]) cout << endl << ve[i].idx ;}return 0;
}思路来源,
思路来源2
