poj 1094 Sorting It All Out (拓撲排序)

    只是利用拓撲排序來計算！每加一個表達式就計算出他的拓撲排序：

    1，不存在拓撲排序，就是表明這些表達式存在矛盾

    2，如果存在唯一的拓撲排序，就可以輸出結果

    3，如果不存在唯一的排序，即存在入度相同的點，此時表示不能確定排序關系或者存在結果矛盾（所以在不能確定排序的時候，還要判斷是不是存在環，從而確定是不是存在拓撲排序）

[cpp]
#include <iostream>  
//#include <fstream>  
using namespace std; 
#define MAX 30  
/*340K  16MS*/  
//var  
int n; 
int a[MAX][MAX]; 
bool flag1,flag2; //flag1代表發現矛盾，flag2代表出現想要的結果  
char s[MAX];  
//fstream fin;  
 
//function  
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)); 
        flag1=flag2=false; 
        int count=0; 
         
        char b1,b2; 
        for(int i=0;i<m;i++) 
        { 
            cin>>b1>>b2>>b2; 
            if(flag1||flag2)  continue; 
            if(a[b1-'A'][b2-'A']==0) 
            { 
                a[b1-'A'][b2-'A']=1; 
                //計算出拓撲排序  
                toposort();  
            }  
            ++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; 
} 
 
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]++; 
      
     for(int i=0;i<n;i++) 
     {  
             //入度為0的點   
             int t=-1; 
             for(int j=0;j<n;j++) 
             { 
                     if(ind[j]==0&&t==-1) 
                          t=j;  
                     else if(ind[j]==0&&t!=-1) 
                     {    
                         //當存在多個入度為0的點時還是要記得去判斷是不是存在環   
                          for(int kk=0;kk<n;kk++) 
                             for(int ii=0;ii<n;ii++) 
                                for(int jj=0;jj<n;jj++) 
                                   if(a[ii][jj]||a[ii][kk]&&a[kk][jj]) 
                                      a[ii][jj]=1; 
                                    
                          for(int ii=0;ii<n;ii++) 
                             if(a[ii][ii]) 
                                flag1=true; 
                                 
                          return;}   //代表有多個入度為0的點，即不能夠進行排序   
             } 
             if(t==-1) 
                 {flag1=true;return;}        //代表存在著環  
                
             //相應的邊對應的度減一  
             for(int j=0;j<n;j++) 
                  if(a[t][j]==1) 
                       ind[j]--;  
              
             ind[t]--;     
             s[i]='A'+t; 
     }  
     flag2=true; 
     s[n]='\0'; 
}