拓扑排序(一种给定的特殊排序)

拓扑排序关键在于需要维护一个入度为0的顶点的集合.(只出不入)

一种特殊的排序方法,什么时候用到拓扑排序了,就是当给定了一种特殊的先后顺序时,叫你以某种方式输出给顺序时就要想到用拓扑排序（比如）.然后拓扑排序当然也可以用数组直接进行模拟,但是时间不是这么的快,所以用模拟邻接表的方式（这个是最快,最省空间的）来写,然后根据题目需要选取适当的优先队列来模拟,虽然过程比较复杂,但是时间会快很多.!

注：当你用数组和vector要爆时,就用数组模拟临接链表的方式,就不会爆了.(对应的vector比对应的数组更省空间.)

比如一道水题点这里

---思路: 明显给定了一个先后顺序,有叫输出特定顺序,所以首先想到拓扑排序.因为要求序号小的排前面,所以选取最小优先队列.然后用一个vector（或一维数组）来存答案在输出就可以了.

AC代码如下:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
using namespace std;
const int maxn=505;
const int eps=1e-6;
const int inf=1e9;
const ll INF=1e15;
int n,m;
priority_queue<int,vector<int>,greater<int> >q;  //以最小值优先的优先队列.
// 因为要求号数小的先出来.所以用最小值优先的队列.
struct node
{
    int w;
    int next;
}s[maxn*maxn];

int head[maxn];
int in[maxn];
int cnt;

void add(int a,int b)
{
    s[cnt].w=b;
    s[cnt].next=head[a];
    head[a]=cnt++;
}  //建立临接链表.

void bfs()
{
    vector<int >v;  //将结果保存在以为vector容器中.
    while(!q.empty())
    {
        int now=q.top();
        q.pop();
        v.push_back(now);
        for(int i=head[now];i!=-1;i=s[i].next){
            int next=s[i].w;   //next为这个点所指向的一个点.
            in[next]--;    //使这个点的入度减一.
            if(!in[next])   //继续吧入度为零的点加到队列中去.
                q.push(next);
        }
    }
    //printf("%d\n",v.size());
    for(int i=0;i<v.size();i++){
        printf("%d%c",v[i],i==v.size()-1?'\n':' ');
    }
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF){
        CLR(in);
        memset(head,-1,sizeof(head));
        CLR(s);
        while(!q.empty())
            q.pop();
        cnt=0;
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            add(u,v);
            in[v]++;   //被指向的那个点入度+1.
        }
        for(int i=1;i<=n;i++){
            if(in[i]==0)   //将全部入度为0的点全部加到队列中去.
                q.push(i);
        }
        bfs();
    }
}