Algorithm 版 (精华区)

发信人: xiong (阿拉斯加棕熊), 信区: Algorithm
标  题: 1097K-Code the Tree-ZJU
发信站: 哈工大紫丁香 (2002年10月12日12:28:04 星期六), 站内信件

#include "stdio.h"
#include "iostream.h"
#include "fstream.h"
int main(void)
{
 char temp;
 int totalnumber=0;//这个是用来纪录输入的总case数的
 int fix;
 int current,old,number;
 int stack;
 //ifstream fin;
 //ofstream fout;
 //最多不超过50个节点，我是从下标1开始的
 bool link[51][51],alive[51];
 int parent[51],edge[51];
 int i,j;
 //fin.open("e:\\in.txt");
 //fout.open("e:\\out.txt");
 while(cin>>temp)
 {
  for(i=1;i<51;i++)
  {
   alive[i]=false;
   edge[i]=0;
  }
  for(i=1;i<51;i++)
  {
   for(j=1;j<51;j++)
   {
    link[i][j]=false;
   }
  }
  stack=1;
  number=1;
  cin>>current;
  parent[current]=0;
  alive[current]=true;
  //输入并初始化这棵树
  while(true)
  {
   cin>>temp;
   if(temp=='(')
   {
    number++;
    old=current;
    cin>>current;
    parent[current]=old;
    link[current][old]=true;
    link[old][current]=true;
    edge[current]++;
    edge[old]++;
    alive[current]=true;
    stack++;
   }
   else
   {
    stack--;
    current=parent[current];
   }
   if(stack==0)
    break;
  }
  fix=number;//纪录总节点数
  //我开始以为需要判断节点是否为一，
  //其实这是没必要的
  //循环并砍掉叶子
  while(number>1)
  {
   for(i=1;i<51;i++)
   {
    //如果是叶子
    if((alive[i]==true)&&(edge[i]==1))
    {
     for(j=1;j<51;j++)
     {
      if(link[i][j]==true)
      {
       if(number>2)
        cout<<j<<" ";
       else
        cout<<j;
       break;
      }
     }
     //砍掉叶子
     alive[i]=false;
     //减少节点数
     number--;
     for(j=1;j<51;j++)
     {
      if(link[i][j]==true)
      {
       //方便起见，两个都砍断
       link[i][j]=false;
       link[j][i]=false;
       //减少与叶子相连的
       //唯一的节点的拥有的边数
       edge[j]--;
      }
     }
     break;
    }
   }
  }
  //单一节点是否有输出？
  //if(fix>1)
   //printf("\n");
   cout<<endl;
  totalnumber++;
 }
 return 0;
}
--

                    为了民族的尊严    为了祖国的明天

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]