• 题目大意: 给出一堆树,求同构(拓扑结构相同)树的集合
• 思路: 一开始写了个前序求置换序列,然后对比后序是否相等,但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

Vijos1683 有根树的同构问题

原文：https://www.cnblogs.com/xxrlz/p/11228221.html