PKU 2568 Decode the Tree
http://poj.org/problem?id=2567
特殊な形式で根なしの木が与えられるので、パースしてリストっぽく出力しろというような問題。
具体的には、最初に与えられた木のノードが1つになるまで、葉であるノードのうち一番小さい番号を持つものを取り除いていき、そのときに取り除いたノードに隣接しているノードの番号を出力していったものが入力になっているというような問題。
こういうのは好きです。楽しい。
素の入力から復元するのは流石に自分には無理なので、一度グラフを構築して出力しています。
入力のたびにいちいち初期化するのが面倒くさかったので、グラフをvector
bool vis[100]; void pr(const vector<vector<int> > &G,int v){ vis[v]=true; cout<<'('<<v+1; FOR(it,G[v]){ if(vis[*it])continue; cout<<' '; pr(G,*it); } cout<<')'; } void solve(const string &in){ vector<int> num; stringstream ss(in); int t; while(ss>>t)num.pb(t-1); vector<vector<int> > G(SZ(num)+1,vector<int>()); set<int> app; rep(i,SZ(num)+1)app.insert(i); FOR(it,num)app.erase(*it); rep(i,SZ(num)){ int u=*app.begin(); app.erase(u); int v=num[i]; G[u].pb(v); G[v].pb(u); if(num.end()==find(num.begin()+i+1,num.end(),num[i]))app.insert(num[i]); } memset(vis,0,sizeof(vis)); pr(G,0); cout<<endl; } main(){ string in; while(getline(cin,in))solve(in); }