题意: 给一个字符串,表示一颗树,要求你把它整理出来,节点从1开始编号,还要输出树边。
解法: 模拟即可。因为由括号,所以可以递归地求,用map存对应关系,np存ind->name的映射,每进入一层括号,使father = now, 遇到右括号’)’,则father = fa[father],用vector存每个节点的子节点,然后最后dfs输出即可。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define N 50017string ss,tmp,S;
string np[N];
map<string,int> mp;
int fa[N],father,ind;
vector<int> G[N];void Go(int u,int v,int father)
{
tmp = "";
int j;
for(int i=u;i<v;i++)
{
if(ss[i] >= 'a' && ss[i] <= 'z')
tmp += ss[i];
else if(ss[i] == '(' || ss[i] == ',' || ss[i] == ')')
{
if(tmp == "") continue;
mp[tmp] = ++ind;
np[ind] = tmp;
tmp = "";
fa[ind] = father;
G[father].push_back(ind);
if(ss[i] == '(')
{
int cnt = ;
for(j=i+;j<v;j++)
{
if(ss[j] == '(') cnt++;
else if(ss[j] == ')')
{
cnt--;
if(cnt == ) break;
}
}
Go(i+,j,ind);
i = j;
}
else if(ss[i] == ')')
father = fa[father];
}
}
if(tmp != "")
{
mp[tmp] = ++ind;
np[ind] = tmp;
tmp = "";
fa[ind] = father;
G[father].push_back(ind);
}
}void dfs(int u)
{
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
printf("%d %d\n",u,v);
dfs(v);
printf("%d %d\n",v,u);
}
}int main()
{
int t,i,j,len;
scanf("%d",&t);
while(t--)
{
mp.clear();
for(i=;i<=;i++)
G[i].clear();
cin>>ss;
len = ss.length();
father = ;
ind = ;
Go(,len,);
printf("%d\n",ind);
for(i=;i<=ind;i++)
cout<<np[i]<<endl;
dfs();
puts("");
}
return ;
}