九度OJ 1359：大魏树遍历（树）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：299

解决：29

题目描述：: 大魏是JOBDU技术组里最喜欢折腾的一个了，单反、骑车、改九度页面，当然还有YY prado。我们姑且先把这些看做是会享受生活的表现；但是有一点我们就不能忍了，他连遍历树都有一些不一样的要求：

1. 对于给定的一棵树，他要求从根节点开始遍历完所有节点，相对于一般的节点遍历，他要求边的遍历，即每条边都要正好遍历过两次

2. 除了对于边遍历的变态要求，他还对叶子节点的遍历序列有着特殊的要求，即会预先指定所有叶子节点的遍历先后顺序。

这些要求是不是很BT? 实际上也还好了，仔细想想也能做出来的。

输入：: 每个测试文件包含多个测试案例，每个测试案例包含三个部分：

第一行为一个整数K，代表这棵树总的节点个数, K>=1并且K<=300。

接下来是K – 1行，每行有两个整数，代表这棵树的K – 1条边。树节点的标号从1开始，且1代表根节点。

最后一行为包含所有的叶子节点编号的一个整数序列，代表大魏所指定的叶子节点的遍历顺序。

输出：: 对于每个测试案例，若满足大魏规定条件的遍历序列存在，则输出这个序列，每两个节点之间由空格隔开，末尾没有空格。

若不存在，则只需要输出一个-1。

样例输入：

样例输出：

1 2 3 2 1

-1

代码：

#include <stdio.h>

#include <string.h>

#define N 301

int n,head[N],li[N],ri[N];

int e,nx[N-1],to[N-1];

int vti[N],mk[N],ln;

int err,f1;

int Tsort(int rt)

{

    int l=N,r=-1,ct=0,eg,peg,sn,es,pes;

    if(head[rt]==0){

        l=r=vti[rt];

        ct=1;

    }

    else{

        for(peg=0,eg=head[rt];eg;peg=eg,eg=nx[eg]){

            sn=to[eg];

            ct+=Tsort(sn);

            if(err) return 0;

            for(pes=0,es=head[rt];li[to[es]]<li[sn];pes=es,es=nx[es]) ;

            if(es!=eg){

                nx[peg]=nx[eg];

                nx[eg]=es;

                if(pes!=0) nx[pes]=eg;

                else head[rt]=eg;

                eg=peg;

            }

            if(li[sn]<l) l=li[sn];

            if(ri[sn]>r) r=ri[sn];

        }

    }

    if(r-l+1==ct){

        li[rt]=l;

        ri[rt]=r;

        return ct;

    }

    else{

        err=1;

        return 0;

    }

}

void printPT(int rt)

{

    int eg;

    if(f1) printf("%d",rt),f1=0;

    else printf(" %d",rt);

    if(head[rt]!=0){

        for(eg=head[rt];eg;eg=nx[eg]){

            printPT(to[eg]);

            printf(" %d",rt);

        }

    }

}

int main()

{

    int i,rt,sn,v;

    while(scanf("%d",&n)!=EOF){

        err=0; e=1; ln=n; f1=1;

        memset(head,0,sizeof(head));

        memset(mk,0,sizeof(mk));

        mk[1]=1;

        for(i=0;i<n-1;i++){

            scanf("%d%d",&rt,&sn);

            if(mk[sn]){v=sn;sn=rt;rt=v;}

            to[e]=sn; nx[e]=head[rt]; head[rt]=e++;

            if(mk[rt]==1) mk[rt]=2,ln--;

            mk[sn]=1;

        }

        for(i=1;i<=ln;i++){

            scanf("%d",&v);

            vti[v]=i;

        }

        Tsort(1);

        if(err) printf("-1");

        else printPT(1);

        printf("\n");

    }

    return 0;

}

/**************************************************************

    Problem: 1359

    User: lovai

    Language: C

    Result: Accepted

    Time:40 ms

    Memory:916 kb

****************************************************************/

巴特西

九度OJ 1359：大魏树遍历（树）

最新文章

热门文章

巴特西

九度OJ 1359：大魏树遍历 （树）

最新文章

热门文章

九度OJ 1359：大魏树遍历（树）