以前的代码有问题,我改了一下,可是还是wa啊! 
大大们怎么一直都不理我我啊? 能不能给份数据我啊? 

各位大虾有谁用 拓扑 过了这题的能贴个代码或是给我发一份吗？ 
我的email: cugcw@2002.cug.edu.cn 


#include<iostream.h> 
#include<string.h> 

char letter[26]; 
int n,m,p,q,indeg[26],relation[26][26],tmpindeg[26],flag,out[26]; 

int search(char *let,char letter)//判断结点在数组中的序号 
{ 
   int h=0; 
   while(h<n&&let[h]!=letter) 
      h++; 
   return h; 
} 

/*--------拓扑排序--------*/ 
void topusort(int *indeg,int *t) 
{ 
   memset(out,-1,26); 
   int total,tmpadd,j,totaln=0; 
   for(j=0;j<n;j++) 
   { 
      for(p=0;p<n;p++) 
      { 
         if(indeg[p]<0) continue; 
         total=0;//已经决定的节点个数 
         for(q=0;q<n;q++) 
            if(indeg[q]==0) 
            { 
               total++;//入度为0的结点的个数 
               tmpadd=q;//入度为0的节点位置 
            } 
         if(total==0)//入度为0的结点的个数为0，即图中存在环，本次排序肯定失败 
         { 
            flag=*t;//flag为失败时的比较次数 
            break; 
         } 
         else if(total>1)//入度为0的结点的个数大于1，则无法判断，继续本次排序 
         { 
            flag=0;//flag=0表示还没有决定 
            break; 
         } 
         else if(total==1)//入度为0的结点的个数为1，则将该结点传给 out数组 
         { 
            out[totaln]=tmpadd;//保存输出序列    
            totaln+=1; 
            if(totaln==n) 
               flag=*t;//flag为成功时的比较次数 
            else flag=0; 
            indeg[tmpadd]=-5;//标志该结点已经处理 
            for(q=0;q<n;q++) 
            { 
               if(relation[q][tmpadd]==1) 
                  tmpindeg[q]--;//根据关系表更改入度数组 
            } 
         } 
      } 
      if(p!=n) break; 
   } 
} 

int main() 
{ 
   char instr[4]; 
   int add1,add2,totaln,i; 
   cin>>n>>m; 
   while(n!=0||m!=0) 
   { 
      memset(relation,0,sizeof(relation)); 
      memset(indeg,-1,sizeof(indeg)); 
      memset(letter,'0',sizeof(letter)); 
      totaln=0;//已经出现的结点个数    
      flag=0; 
      for(i=1;i<=m;i++) 
      { 
         cin>>instr; 
         if(flag==0)//flag=0表示还没有出错或还没有决定顺序 
         { 
            add1=search(letter,instr[0]); 
            add2=search(letter,instr[2]);       
            if(add1==n) 
            { 
               add1=totaln; 
               totaln++; 
               indeg[add1]=0; 
            } 
            if(add2==n) 
            { 
               add2=totaln; 
               totaln++; 
               indeg[add2]=0; 
            }//如果该结点是第一次出现       
            letter[add1]=instr[0]; 
            letter[add2]=instr[2];//保存结点信息 
            if(relation[add2][add1]==1)   //如果这对关系已经出现过，则无需重复 
               continue; 
            relation[add2][add1]=1; 
            indeg[add2]+=1;//添加关系及入度 
            for(p=0;p<26;p++) 
               tmpindeg[p]=indeg[p];//COPY一个入度数组传给拓扑排序函数          
            topusort(tmpindeg,&i); 
         } 
         else continue; 
      } 
      if(flag==0&&i==m+1) 
         cout<<"Sorted sequence cannot be determined."<<endl; 
      else if(p!=n&&i==m+1) 
         cout<<"Inconsistency found after "<<flag<<" relations."<<endl; 
      else if(p==n&&i==m+1) 
      { 
         cout<<"Sorted sequence determined after "<<flag<<" relations: "; 
         for(i=0;i<n;i++) 
            cout<<letter[out[i]]; 
         cout<<"."<<endl; 
      } 
      cin>>n>>m; 
   } 
}

• Re:我用拓扑怎么就是过不了呢? 晕了好久,大家帮帮小弟啦!! (8) cugwei 2004-06-09 15:35:06
• up up up!!! (22) cugwei 2004-06-10 15:56:25
• AC 啦 (37) cugwei 2004-06-11 00:19:15
  • cong~~~~~~~~ (41) pladene 2004-06-11 15:39:02