1097 code the tree.txt

浙江大学ACM练习题 1097 提交通过原代码

#include <cstdio>
#include <memory.h>
#include <cctype>
#define MAXN 100

int degree[MAXN];
bool adj[MAXN][MAXN];
int n;
int ni;
char line[1000];

void make(int root,int &k)
{
     if (root>n) n=root;
     while (line[k]=='(')
     {
           int now;
           k++;
           sscanf(line+k,"%d",&now);
           while (isdigit(line[k])) k++;
           degree[root]++;
           degree[now]++;
           adj[root][now]=adj[now][root]=true;
           make(now,k);
           k++;
     }
     return;
}

int main()
{
    char ch;
    int len;
    int i,j,k;
    while (scanf("%c",&ch)!=EOF)
    {
          len=0;
          k=0;
          memset(line,0,sizeof(line));
          memset(degree,0,sizeof(degree));
          memset(adj,false,sizeof(adj));
          while (ch!=10)
          {
                while (ch==' ') scanf("%c",&ch);
                if (ch!=10)
                {
                    line[len]=ch;
                    len++;
                    scanf("%c",&ch);
                }
          }
          n=0;
          make(0,k);
          for (i=1;i<=n;i++)
          if (adj[0][i])
          {
              adj[0][i]=adj[i][0]=false;
              degree[i]--;
              break;
          }
          
          
          ni=0;
          while (++ni<n)
          {
                for (i=1;i<=n;i++) if (degree[i]==1) break;
                for (j=1;j<=n;j++) if (adj[i][j])
                {
                    adj[i][j]=adj[j][i]=false;
                    degree[j]--;
                    printf("%d",j);
                    if (ni<n-1) putchar(' ');
                    break;
                }
                degree[i]--;
          }
          putchar('\n');
    }
    return 0;
}