有向树同构括号序列

本是古典何须时尚 2021-10-23 14:14 220阅读 0赞

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    int n,mn,m,cnt;
    int bel[55],siz[55],to[110],next[110],head[55],mx[55];
    string f[55],p[55],g[55];
    inline int rd()
    {
        int ret=0,f=1;  char gc=getchar();
        while(gc<'0'||gc>'9') {if(gc=='-')    f=-f;   gc=getchar();}
        while(gc>='0'&&gc<='9')   ret=ret*10+(gc^'0'),gc=getchar();
        return ret*f;
    }
    inline void add(int a,int b)
    {
        to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
    }
    void dfs(int x,int fa)
    {
        int i,sum=0;
        for(i=head[x];i!=-1;i=next[i])  if(to[i]!=fa)   dfs(to[i],x);
        for(i=head[x];i!=-1;i=next[i])  if(to[i]!=fa)   p[++sum]=f[to[i]];
        f[x]="(";
        sort(p+1,p+sum+1);
        for(i=1;i<=sum;i++)  f[x]+=p[i];
        f[x]+=")";
    }
    void getrt(int x,int fa)
    {
        mx[x]=0,siz[x]=1;
        for(int i=head[x];i!=-1;i=next[i])  if(to[i]!=fa)   getrt(to[i],x),siz[x]+=siz[to[i]],mx[x]=max(mx[x],siz[to[i]]);
        mx[x]=max(mx[x],m-siz[x]);
        mn=min(mn,mx[x]);
    }
    string get()
    {
        string tmp="";
        m=rd();
        int i,a;
        memset(head,-1,sizeof(head)),cnt=0;
        for(i=1;i<=m;i++)
        {
            a=rd();
            if(a)   add(a,i),add(i,a);
        }
        mn=1<<30,getrt(1,0);
        for(i=1;i<=m;i++)    if(mx[i]==mn)
        {
            dfs(i,0);
            tmp=max(tmp,f[i]);
        }
        return tmp;
    }
    int main()
    {
        n=rd();
        int i,j;
        for(i=1;i<=n;i++)    g[i]=get();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<i;j++) if(g[i]==g[j])  break;
            printf("%d\n",j);
        }
        return 0;
    }//4 4 0 1 1 2 4 2 0 2 3 4 0 1 1 1 4 0 1 2 3

洛谷：树的同构

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的同构判断

一题意理解给定两颗树，T1，T2，若T1可以通过若干次的左右子互换变成T2，则称为这两棵树同构。二输入数据先输入一个N，代表接下来的个数，然后輸入N组元素，

小鱼儿/ 2023年07月02日 11:30/ 0 赞/ 88 阅读

相关 03-树1 树的同构

笔记： include<stdio.h> define MaxTree 10 define ElementType char def

亦凉/ 2022年07月28日 05:09/ 0 赞/ 122 阅读

相关 03-树1 树的同构

include<stdio.h> define MaxTree 10 define ElementType char define T

男娘i/ 2022年07月28日 05:08/ 0 赞/ 118 阅读

相关《数据结构》03-树1 树的同构

题目给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G

àì夳堔傛蜴生んèń/ 2022年05月15日 15:00/ 0 赞/ 163 阅读

相关同构数

今天突然看到了关于同构数的问题，试着理解了一下同构数的概念：正整数n若是它平方数的尾部，则称n为同构数。例如：5的平方数是25，且5出现在25的右侧，那么5就是一个

怼烎@/ 2022年04月04日 10:42/ 0 赞/ 253 阅读

相关同构字符串

题目描述给定两个字符串 s 和 t，判断它们是否是同构的。如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换

小灰灰/ 2021年12月14日 03:07/ 0 赞/ 257 阅读

相关树的同构

这里给出一种O（N）判断两棵树是否同构的方法：首先找出两个树的重心，然后对这个重心进行树的哈希。然后比对哈希结果，没有找到例题，但是有一个判断多棵树是否同构的例题，因为

谁践踏了优雅/ 2021年11月04日 10:26/ 0 赞/ 298 阅读

相关 P5043 【模板】树同构（[BJOI2015]树的同构）

[传送门][Link 1] 哈希 $dfs$ 枚举所有节点，进入时哈希值加一个左括号，把所有儿子哈希值加入，退出时加一个右括号因为儿子的顺序可以任意，所以要把儿子哈希值

喜欢ヅ旅行/ 2021年10月29日 09:30/ 0 赞/ 263 阅读

相关 pta 编程题6 树的同构

其它pta数据结构编程题请参见：[pta][] 题目请参见：[树的同构][Link 1] 因题目中左右子树是按照下标给出，因此用数组存放树是更好的方法。判断两棵树是否同

逃离我推掉我的手/ 2021年10月24日 01:52/ 0 赞/ 233 阅读

相关有向树同构括号序列

include <cstdio> include <cstring> include <iostream> include <algorithm

本是古典何须时尚/ 2021年10月23日 14:14/ 0 赞/ 221 阅读