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++ ,