NYOJ 496题巡回赛（拓扑排序）

题目链接~~>

             还没学拓扑排序时就做过这题，没过之后就一直放那，学习了拓扑排序后才想起这题，1A。

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int topo[30],n;
     
    
   

    

     

    
    

     

      char g[30][30];
     
    
   

    

     

    
    

     

      char s[30];
     
    
   

    

     

    
    

     

      int toposort()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int f=0,t=0,q,i,j,mat;
     
    
   

    

     

    
    

     
 for(i=0;i<n;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=0;q=0;
     
    
   

    

     

    
    

     
 for(j=0;j<n;j++)
     
    
   

    

     

    
    

     
 if(topo[j]==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mat=j;
     
    
   

    

     

    
    

     

       q++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(q>1||q==0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     
 if(q==1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=1;
     
    
   

    

     

    
    

     

       s[t++]=mat+65;
     
    
   

    

     

    
    

     

       topo[mat]=-1;
     
    
   

    

     

    
    

     
 for(int k=0;k<n;k++)
     
    
   

    

     

    
    

     
 if(g[mat][k]==1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       topo[k]--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       s[t++]='\0';
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i,m;
     
    
   

    

     

    
    

     
 char ch1,ch2;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(g,0,sizeof(g));
     
    
   

    

     

    
    

     
 memset(topo,0,sizeof(topo));
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&m);
     
    
   

    

     

    
    

     

       getchar();
     
    
   

    

     

    
    

     
 for(i=0;i<m;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%c %c",&ch1,&ch2);
     
    
   

    

     

    
    

     

       getchar();
     
    
   

    

     

    
    

     

       g[ch1-65][ch2-65]=1;
     
    
   

    

     

    
    

     

       topo[ch2-65]++;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(toposort())
     
    
   

    

     

    
    

     
 puts(s);
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 printf("No Answer\n");
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/9412231