poj 1094 拓扑排序

àì夳堔傛蜴生んèń 2021-11-02 14:24 269阅读 0赞

悲剧，这题错得好惨，首先这题题意就没仔细看清，误读题意。

读懂题意后又悲剧了，当不确定时还要判断是否有回路。

判断回路时又用了错误算法，思考不认真，当然知道可以用Floyd传递闭包判断就是没用。

自以为题目不会那么麻烦，直接判断入度就可以了。自己得想法真的太二。怎么可以用判断入度就可以判断有无回路呢？

正确算法：

1.边输入边（A《B）就要边处理。先判断是否有冲突，然后判断是否不确定。

确定冲突或答案后只要把后面得数据读进来就可以，不用处理。

2.拓扑排序算法

3.Floyd判断是否有回路

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int mp[30][30];
    int indegree[30];
    int sorted[30];
    int hash[30];
    int N,M,e;
    
    int floyd( )
    {
      int fp[30][30];
      for( int i = 0; i < 30; i++)
       for( int j = 0; j < 30; j++)
          fp[i][j] = mp[i][j];
    
      for( int k = 0; k < 26; k++)
       for( int i = 0; i < 26; i++)
        for( int j = 0; j < 26; j++)
                if( fp[i][k] && fp[k][j] )
           fp[i][j] = fp[i][k] & fp[k][j];
    
      for( int i = 0; i < 26; i++)
        if( fp[i][i] == 1 )
        return 0;
      return 1;
    }
    
    int toplogical( )
    {
       int degree[30], p, f, num;
       e = 0;
       for( int i= 0; i < 30; i++)
         degree[i] = indegree[i];
       while(e < N )
       {   
           f = 0;
           num = 0;
         //  memset(record, 0, sizeof(record));
           for( int i = 0; i < 26; i++)
           {
             if( hash[i] && degree[i] == 0)
         {
               f++;
               p = i;
             }
             if( hash[i] && degree[i] != -1)
               num++;
                  
           }
           if( f == 0 && e < N && num == 0)
           return 0;
           if( f > 1 ) //情况不确定时还要判断时否有环
           {  
              if( floyd() )
            return 0;
              return 3;
           }
           degree[p] = -1;
           sorted[e++] = p;
           for( int i = 0; i < 26; i++)
           {
              if( hash[i] && mp[p][i] )
              {
                    degree[i]--;
              }
           }
    
       }
       return 1; 
    }
    
    void debug( )
    {
      freopen("in.txt","r", stdin);
      freopen("out.txt","w", stdout);
    
    }
    
    int main( )
    {
      char str[30];
     // debug( );
      while( scanf("%d%d",&N, &M), N + M )
      {
         memset(mp, 0, sizeof(mp));
         memset(indegree, 0, sizeof(indegree));
         memset(hash, 0, sizeof(hash));
         int f = 0, ans;
         for( int i = 1; i <= M; i++)
         {
             scanf("%s",str);
             if( !f )
               {
              int a = str[0] - 'A';
              int b = str[2] - 'A';
              hash[a] = 1, hash[b] = 1;
              if( mp[a][b] ) continue;
              mp[a][b] = 1;
              indegree[b]++;
              ans = i;
              //判断是否成环,冲突
              if( toplogical() == 3 ) {  f = 3;  continue;}
    
             //判断情况是否确定
              if( toplogical() ) { f = 2; continue; }
        
             }
        
         }
         if( f == 2 )
         {
        printf("Sorted sequence determined after %d relations: ", ans);
            for(int i = 0; i < e; i++)
            printf("%c", 'A' + sorted[i]);
            printf(".\n");
         }
         else if( f == 0 )
            printf("Sorted sequence cannot be determined.\n");
         else if( f== 3 )
        printf("Inconsistency found after %d relations.\n", ans);
      }
      return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/13/2589971.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/1384d9d04c8a48f9b6e80152ea8e9e88.png