poj 1094 Sorting It All Out(圖論)

這一題，看了個大牛的解題報告，思路變得非常的清晰：

1，先利用floyd_warshall算法求出圖的傳遞閉包

2，再判斷是不是存在唯一的拓撲排序，利用出度和入度是不是相加為n-1

3，利用拓撲排序求出當前的圖形的唯一的拓撲排序

一開始我的思路跟上述的差不多，但是沒有利用floyd_warshall算法求出傳遞閉包，准備著利用拓撲排序求出是不是存在著有環回路，我覺得我的這個思路也是可以的。等一下我會將我的這個思路給寫成程序。在我的百度雲中有這個程序的測試數據（來自poj）

#include <iostream>
//#include <fstream>
using namespace std;
#define MAX 30
/*396K	16MS*/
//var
int a[MAX][MAX];
int n;
int flag1,flag2;  //falg1代表的是當前有環的錯誤，即存在錯誤的排序 
char s[MAX];     //存放最後的結果 
//fstream fin;
//function
bool transition();
bool judge();
void toposort();

//main函數 
int main()
{
    //fin.open("1094.txt",ios::in);
    int m;
    while(cin>>n>>m)
    {
         if(n==0&&m==0)  break;
         memset(a,0,sizeof(a));
         int count=1;
         flag1=flag2=false;
         for(int i=0;i<m;i++)
         {
            char b1,b2;
            cin>>b1>>b2>>b2;
            if(flag1||flag2) continue; 
            if(a[b1-'A'][b2-'A']==0)
            {
                a[b1-'A'][b2-'A']=1;
                //求傳遞閉包,判斷是不是有環，這樣就知道是不是存在著錯誤的答案 
                if(!transition()){flag1=true;continue;}
                //判斷是不是存在著唯一的拓撲排序 
                else if(judge())
                {
                     toposort();
                     flag2=true;
                     continue;
                } 
            }
            ++count;
         }
         
         if(flag1)
            cout<<"Inconsistency found after "<<count<<" relations."<<endl;
         else if(flag2)
            cout<<"Sorted sequence determined after "<<count<<" relations: "<<s<<"."<<endl;
         else
            cout<<"Sorted sequence cannot be determined."<<endl;
    }
    system("pause");
    return 0;
}

//求傳遞閉包
bool  transition()
{
      for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
              if(a[i][j]==1||a[i][k]==1&&a[k][j]==1)
                 a[i][j]=1;
                 
      for(int i=0;i<n;i++)
         if(a[i][i]==1)
           return false;
      return  true;
}

//計算是不是存在著唯一的拓撲排序
bool judge()
{
     int *ind=new int[n];
     int *outd=new int[n];
     memset(ind,0,sizeof(int)*n);
     memset(outd,0,sizeof(int)*n);
     for(int i=0;i<n;i++)
     {
             for(int j=0;j<n;j++)
             {
                     if(a[i][j])
                     {
                         ind[j]++;
                         outd[i]++;
                     }
             }
     }
    
     for(int i=0;i<n;i++)
       if(ind[i]+outd[i]<n-1)
          return false;
       return true;
} 

//拓撲排序的實現 
void toposort()
{
     //按照入度來進行計算
     int *ind=new int[n];
     memset(ind,0,sizeof(int)*n);
     for(int i=0;i<n;i++)
     {
             for(int j=0;j<n;j++)
                   if(a[i][j]==1)
                      ind[j]++;
     } 
     
     //求出入度後計算出當前的的拓撲排序的結果
     int t=n;
     for(int i=0;i<n;i++)
     {
             int j;
             for(j=0;j<n;j++) 
                 if(ind[j]==0)
                 { ind[j]--; s[i]=j+'A'; break;}
             int t=j;
             for(j=0;j<n;j++)
                 if(a[t][j]==1)
                     ind[j]--;
     } 
    
     s[n]='\0';
}