UVA 10410 Tree Reconstruction

UVA 10410 Tree Reconstruction

題目概述:

給一棵樹的BFS,DFS的路徑，請還原整棵樹，若答案多解，輸出其一即可。

入門經典書p.6-50

思路:

以範例當作例子

不斷的利用BFS的順序，將樹還原回來。

//By SCJ

//uva 10410

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000

#define endl '\n'

vector<int> G[maxn+2];

int n,bfs[maxn+2],dfs[maxn+2];

struct P{

   int root,l,r;

};

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   while(cin>>n)

   {

       for(int i=0;i<n;++i) cin>>bfs[i];

       for(int i=0;i<n;++i) cin>>dfs[i];

       queue<P> Q;

       Q.push({dfs[0],1,n-1});

       int now=1;

       while(Q.size())

       {

           P p=Q.front();Q.pop();

           int la=p.l;

           G[p.root].push_back(dfs[p.l]);now++;

           for(int i=p.l+1;i<=p.r;++i)

           {

               if(dfs[i]==bfs[now])

               {

                   if(la+1<=i-1) Q.push({dfs[la],la+1,i-1});

                   G[p.root].push_back(dfs[i]);

                   la=i;now++;

               }

               else if(i==p.r) Q.push({dfs[la],la+1,i});

           }

       }

       for(int i=1;i<=n;++i)

       {

           cout<<i<<':';

           for(int j=0;j<G[i].size();++j) cout<<' '<<G[i][j];

           cout<<endl;

       }

       for(int i=0;i<=n;++i) G[i].clear();

   }

}