家谱树 x

 1 #include 
      
       2 #include 
       
        3 #include 
        
         4 #include 
         
          5 
         #define Maxn 101 
          6 
          7 
         using 
         namespace 
          std;  
          8 
          9 
         struct 
          zhan{  
         10 
         int 
          z[Maxn],tops;  
         11 
         void add( 
         int x) 
         // 
         进栈操作  
         12 
          {  
         13 z[++tops]= 
         x;  
         14 
          }  
         15 
         int duitou() 
         // 
         返回队头元素  
         16 
          {  
         17 
         return 
          z[tops];  
         18 
          }  
         19 
         void shan() 
         // 
         删除队头元素  
         20 
          {  
         21 tops-- 
         ;  
         22 
          }  
         23 
         bool kong() 
         // 
         检验栈是否为空  
         24 
          {  
         25 
         return tops == 
         0 ? 
         1 : 
         0 
         ;  
         26 
          }  
         27 zhan () 
         // 
         构造函数(与结构体同名，没有返回值，用于初始化)  
         28 
          {  
         29 tops= 
         0 
         ;  
         30 
          }  
         31 
         }q;  
         32 
         33 
         int 
          n,temp,qwq;  
         34 
         int 
          du[Maxn],chu[Maxn];  
         35 
         int 
          gx[Maxn][Maxn];  
         36 
         37 
         int 
          main()  
         38 
         {  
         39 
         char 
          s;  
         40 scanf( 
         " 
         %d 
         ",& 
         n);  
         41 
         for( 
         int i= 
         1;i<=n;i++ 
         )  
         42 
          {  
         43 
         while(cin>> 
         s)  
         44 
          {  
         45 
         if(s== 
         ' 
         0 
         ') 
         break 
         ;  
         46 
         else 
         47 
          {  
         48 chu[i]++; 
         // 
         表示i有chu[i]条出度  
         49 du[s- 
         ' 
         0 
         ']++; 
         // 
         s入度++  
         50 gx[i][chu[i]]=s- 
         ' 
         0 
         '; 
         // 
         说明i的第几(chu[i])条出度为s  
         51 
          }  
         52 
          }  
         53 
          }  
         54 
         for( 
         int i= 
         1;i<=n;i++ 
         )  
         55 
          {  
         56 
         if(!du[i]) q.add(i); 
         // 
         如果入度为0，进栈  
         57 
          }  
         58 
         do 
         59 
          {  
         60 temp= 
         q.duitou();  
         61 
          q.shan();  
         62 cout< 
         
           " 
          " 
          ;  
          63 
          for( 
          int j= 
          1;j<=chu[temp];j++ 
          )  
          64 
           {  
          65 du[gx[temp][j]]--; 
          // 
          与刚出栈的'temp'有边的入度--  
          66 
          if(!du[gx[temp][j]]) q.add(gx[temp][j]); 
          // 
          如果这个元素的入度为0，进栈  
          67 
           }  
          68 } 
          while(!q.kong()); 
          // 
          终止条件  
          69 
          return 
          0 
          ;  
          70 }