UVA 10410——Tree Reconstruction

水深无声 2022-07-29 09:26 129阅读 0赞

题意：给定一颗树的BFS和DFS，求这棵的每个节点。

思路：用栈模拟维护。对应的BFS为每个节点到根节点的距离，然后比较当前节点和栈顶节点与根的距离，如果当前节点大，则为栈顶节点的孩子，否则弹出继续比较。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000005;
    const int M=1005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define fr(i,s,n) for (int i=s;i<=n;i++)
    
    int v[M];
    vector<int>p[M];
    stack<int>s;
    
    void sol(int q)
    {
        while (1)
        {
            if (v[q]==2||v[q]>1+v[s.top()])
            {
                p[s.top()].push_back(q),s.push(q);
                break;
            }
            else s.pop();
        }
    }
    int main()
    {
        int n,x;
        while (~scanf("%d",&n)&&n)
        {
            fr(i,1,n) scanf("%d",&x),v[x]=i,p[i].clear();
            scanf("%d",&x); s.push(x);
            fr(i,1,n-1) {scanf("%d",&x);sol(x);}
    
            fr (i,1,n)
            {
                printf("%d:",i);
                for (int j=0;j<p[i].size();j++)
                printf(" %d",p[i][j]);
                puts("");
            }
            while (!s.empty()) s.pop();
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 Tree UVA 548(DFS)

解题思路：对于给定的二叉树的中序遍历和后序遍历，可以构造出这棵二叉树，方法是根据后序遍历找到树根。然后在中序遍历中找到树根，从而找出左右子树的结点列表，然后递归构造左

我就是我/ 2024年02月17日 18:51/ 0 赞/ 16 阅读

相关 UVA 536——Tree Recovery

题意：给定一颗树的先根遍历和中根遍历，然后求后根遍历。思路：先根遍历的第一个为root，然后找到root在中根的位置，进而递归左右儿子求解。 code

「爱情、让人受尽委屈。」/ 2022年07月29日 10:34/ 0 赞/ 149 阅读

相关 UVA 10410——Tree Reconstruction

题意：给定一颗树的BFS和DFS，求这棵的每个节点。思路：用栈模拟维护。对应的BFS为每个节点到根节点的距离，然后比较当前节点和栈顶节点与根的距离，如果当前节点大

水深无声/ 2022年07月29日 09:26/ 0 赞/ 130 阅读

相关 UVA 712 S-Tree

![20180225101644700][]![20180225101651457][]![20180225101658191][] 题目解析：没有发现x1，x2等的作用

左手的ㄟ右手/ 2022年05月31日 12:42/ 0 赞/ 131 阅读

相关 uva 10303 - How Many Trees?(卡特兰数）

[题目链接：uva 10303 - How Many Trees?][uva 10303 - How Many Trees] 卡特兰数，公式num\[i + 1\]

迈不过友情╰/ 2022年05月14日 13:52/ 0 赞/ 133 阅读

相关 C - Tree UVA - 548

题目描述： You are to determine the value of the leaf node in a given binary tree that is

Love The Way You Lie/ 2022年03月22日 06:06/ 0 赞/ 121 阅读

相关 Tree UVA - 548 (DFS+建立二叉树)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgx

男娘i/ 2022年02月28日 13:22/ 0 赞/ 183 阅读

相关 S-Trees UVA - 712 (二叉树模拟)

题目太长不贴了:[https://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&page=sho

忘是亡心i/ 2022年02月26日 13:30/ 0 赞/ 177 阅读

相关 Trees on the level UVA - 122 (二叉树建树)

Trees on the level Background Trees are fundamental in many branches of computer scie

左手的ㄟ右手/ 2022年02月24日 09:58/ 0 赞/ 192 阅读

相关 Tree Reconstruction UVA - 10410 (根据树的BFS和DFS建树)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgx

悠悠/ 2022年02月21日 02:11/ 0 赞/ 168 阅读