hdu1532 用BFS求拓扑排序

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1285

题目给出一些点对之间的先后顺序，要求给出一个字典序最小的拓扑排列。对于拓扑排序的问题，我们有DFS和BFS都能够解决，但是问题是DFS只能处理上一层结点和下一层结点相对于根节点之间的距离，也就是说深度就是他们之间的先后顺序，对于同一层的，是没有先后顺序的，但是BFS可以处理同一层之间的先后关系，所以我们考虑用BFS进行遍历，并且将原始BFS求拓扑排序中的队列变成优先队列。这样我们就能在每一层中优先选择字典序小的结点先输出。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define mp(a,b) make_pair((a),(b))

 #define P pair<int,int>

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 const int maxn=;

 int n,m,t;

 inline int read(){

     int ans=,w=;

     char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')w=-;ch=getchar();}

     while(isdigit(ch))ans=(ans<<)+(ans<<)+ch-'',ch=getchar();

     return ans*w;

 }

 struct node{

     int u,v;

 }p[maxn];

 int e;

 int vis[maxn][maxn],head[maxn],nxt[maxn],in[maxn],num[maxn];//in表示入度

 void init()

 {

     e=;

     mem(vis,);mem(head,-);mem(nxt,-);mem(in,);

     mem(num,);//排名信息置零

  }

 void addedge(int u,int v)

 {

     p[e].u=u;

     p[e].v=v;

     nxt[e]=head[u];

     head[u]=e++;

 }

 void topsort()

 {

     priority_queue<int,vector<int> ,greater<int> > q;//最小堆

     f(i,,n)

     {

         if(in[i]==)q.push(i);//将入度为零的点按照字典序排在优先队列中

     }

     int t=,id;//用BFS对付topsort时从队列中出来的点的顺序实际上就是topsort完成之后应该有的排序

     while(!q.empty())

     {

         num[t++]=id=q.top();

         q.pop();

         for(int i=head[id];~i;i=nxt[i])//扫描从这一点出发的所有的边

         {

             in[p[i].v]--;//所到的点的入度减一

             if(in[p[i].v]==)q.push(p[i].v);//将入度为0的点归入优先队列

         }

      }

     //将所有的点都扫描过之后，由于一定存在拓扑序，所以直接输出结果

      pf("%d",num[]);

      f(i,,n-)pf(" %d",num[i]);

      pf("\n");

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     while(scanf("%d%d",&n,&m)!=EOF)

     {

             init();

             int a,b;

             f(i,,m)

             {

                 a=read(),b=read();

                 if(!vis[a][b])//保证两条边之间的只有一条有向边，否则出入度就会发生变化，导致错误

                 {

                     addedge(a,b);

                     vis[a][b]=;

                     in[b]++;

                 }

              }

              topsort();

     }

 }