POJ1635 Subway tree systems（判断树的同构,树的最小表示法）

布满荆棘的人生 2021-12-04 00:45 244阅读 0赞

## 题意：初始时站在树的根节点，若朝着远离根的方向走，记录“0”，接近根的方向走记录“1”。并且树的每一条边只能（必须）来回走一次（即向下和返回）。一个合法的序列可以描述出一棵树的形态。现在给出两个合法的序列，判断两棵树是否同构。   分析：由于根节点确定，若两棵树同构，无非就是把子树的位置交换了一下。很自然的想法就是：将树的子树进行排序，若排序之后两个字符串相等，则同构；否则不同构。   树的括号序列最小表示法可以参考[https://www.byvoid.com/zhs/blog/directed-tree-bracket-sequence][https_www.byvoid.com_zhs_blog_directed-tree-bracket-sequence]。另外还有哈希的做法，不过参数不好拿捏，不推荐使用，只是一个补充，可以参考[https://www.cnblogs.com/kirito520/p/5639722.html][https_www.cnblogs.com_kirito520_p_5639722.html]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long int LL;
    const int N=3000+5;
    int fa[N];
    char a[N],b[N];
    vector<int>ta[N],tb[N];
    void build(char *s,vector<int>tr[N]){
        int cnt=1,now=0,len=strlen(s);
        for(int i=0;i<N;i++) tr[i].clear();
        for(int i=0;i<len;i++){
            if(s[i]=='0'){
                fa[cnt]=now;
                tr[now].push_back(cnt);
                now=cnt++;
            }
            else now=fa[now];
        }
    }
    
    string dfs(int now,vector<int>tr[N]){
        vector<string>res;
        for(int i=0;i<tr[now].size();i++)
            res.push_back(dfs(tr[now][i],tr));
        string ans="(";
        sort(res.begin(),res.end());
        for(int i=0;i<res.size();i++)
            ans+=res[i];
        ans+=")";
        return ans;
    }
    
    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%s",a);
            scanf("%s",b);
            memset(fa,0,sizeof(fa));
            build(a,ta);
            memset(fa,0,sizeof(fa));
            build(b,tb);
            if(dfs(0,ta)==dfs(0,tb)) printf("same\n");
            else printf("different\n");
        }
        return 0;
    }

[https_www.byvoid.com_zhs_blog_directed-tree-bracket-sequence]: https://www.byvoid.com/zhs/blog/directed-tree-bracket-sequence
[https_www.cnblogs.com_kirito520_p_5639722.html]: https://www.cnblogs.com/kirito520/p/5639722.html