拓扑排序bfs的实现既可以使用队列也可以使用栈,当路径唯一时,两者结果并无差异。原因是因为后排的元素是相互独立的。

模板题:http://poj.org/problem?id=1094

思路:

找度为0的元素,入列查找关系

对应关系减度

反复直到队列为空

没太多可说的,难点是应用涉及aoe网,关键路径的那种


大佬代码


#include <iostream>
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,m;
int mp[110][110],in[110],list[110],tm[110];//mp存储关系,in记录初始y的度 ,list是排序存储的空间,tm存储一直延续的度 
int toopsort()
{
    queue<int>s;
    while(!s.empty())
    {
       s.pop();
    }
    int flag=0,j=0;
    memcpy(tm,in,sizeof(in));
    for(int i=0;i<n;i++)
    {
        if(tm[i]==0)
        {
          s.push(i);//找出入度为0得点即为起始点
        }
    }
    while(!s.empty())
    {
         if(s.size()>1)//如果入度为零的点有很多,则很多点还没涉及到还处于初始化中,为1时才只有一个起始点
         {
            flag=1;//不能确定关系则要继续进行
         }
         int t=s.front();
         s.pop();
         list[j++]=t;
         for(int i=0;i<n;i++)
         {
            if(mp[t][i])//t和i有关系
            {
               if(--tm[i]==0)//存储入度为0得点
               {
                  s.push(i);
               }
            }
         }
 
    }
    if(j!=n)//如果j>n则说明有环,应为处理完后加上初始化的入度为0得点应为n个
    return 1;
    else if(flag)//无法确定关系继续
    return 2;
    else return 0;//既没有环又没有不能确定关系的则完成
}
int main()
{
    int flag1,flag2;
    char x,y;
    while(~scanf("%d%d",&n,&m)&&n&&m)
    {
          getchar();
          flag1=0;
          flag2=0;
          memset(mp,0,sizeof(mp));
          memset(in,0,sizeof(in));
          for(int i=1;i<=m;i++)
          {
          scanf("%c<%c",&x,&y);//即使有了结果也要保证全部输入完成
          getchar();
          if(!flag1&&!flag2)//用两个标记变量来确定
          {
 
 
               if(mp[y-'A'][x-'A']==1)//xY和Yx都有,不符合条件 
               {
                  printf("Inconsistency found after %d relations.",i);
                  flag1=1;
                  continue;
               }
               if(mp[x-'A'][y-'A']==0)
               {
                  mp[x-'A'][y-'A']=1;
                  in[y-'A']++;
               }
               int tmp=toopsort();
               if(tmp==1)
               {
                  printf("Inconsistency found after %d relations.",i);
                  flag1=1;
               }
               else if(tmp==0)
               {
                  flag2=1;
                  printf("Sorted sequence determined after %d relations: ",i);
                  for(int j=0;j<n;j++)
                  {
                     printf("%c",list[j]+'A');
                  }
                  printf(".");
               }
          }
 
          }
          if(!flag1&&!flag2)//剩下的情况就是无法判定了
          {
          printf("Sorted sequence cannot be determined.");
          }
          printf("\n");
    }
    return 0;
}