当前位置:编程学习 > C/C++ >>

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; 
                

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,