问题标题: 酷町堂：有哪位大佬知道图论中高大尚拓扑排序的模板？谢谢。

拓扑排序（模板）

第一种模板（使用dfs）

int n, G[maxn][maxn], c[maxn], topo[maxn], t;  
/* 
 *n表示邻接表的个数，  
 *c[]表示状态，为1表示访问过，为0表示未访问，为-1表示正在访问  
 *topo表示排完序的拓扑序列  
 */   
bool dfs(int u){  
    c[u] = -1;  
    for(int v = 0; v < n; v++) if(G[u][v]) {  
        if(c[v]<0)   
            return false;  
        else if(!c[v])   
            dfs(v);  
    }  
    c[u] = 1; topo[--t]=u;  
    return true;  
}  
  
bool toposort(){  
    t = n;  
    memset(c, 0, sizeof(c));  
    for(int u = 0; u < n; u++) if(!c[u])  
    if(!dfs(u)) return false;  
    return true;  
} 

第二种模板（利用出度的想法，入度为0表示第一个放出图的点，同时所有和改点相连的点的入度减一）

int G[MAXN][MAXN];//路径  
int in_degree[MAXN];//入度  
int ans[MAXN];//路径   
int n;//顶点   
void toposort()  
{  
    for(i = 1; i <= n; i++)  
    {  
        for(j = 1; j <= n; j++)  
        {  
            if(G[i][j])  
            {  
                in_degree[j]++;  
            }  
        }  
    }  
    for(i = 1; i <= n; i++)//从最小的开始寻找，  
    {//这样保证了有多个答案时序号小的先输出  
        int k = 1;  
        while(in_degree[k] != 0)//寻找入度为零的点  
            k++;  
        ans[i] = k;  
        in_degree[k] = -1;  
        //更新为-1，后边检测不受影响，相当于删除节点  
        for(int j = 1; j <= n; j++)  
        {  
            if(G[k][j])  
                in_degree[j]--;//相关联的入度减1  
        }  
    }  
}  

图论--拓扑排序模板

拓扑排序是图论中，按照有向边的进入顺序依次排序，在有环的图中不存在拓扑排序。

首先是小白书上的拓扑排序模板，用的是DFS建立拓扑排序，但是似乎除了一般的拓扑排序以外什么都做不了……求字典序最小或者输出全部答案都不适用……

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 const int maxn=1e5+5;
 5 const int maxm=1e5+5;
 6 
 7 int head[maxn],point[maxm],nxt[maxm],size;
 8 int vis[maxm],topo[maxm],t;
 9 
10 void init(){
11     memset(head,-1,sizeof(head));
12     size=0;
13 }
14 
15 void add(int a,int b){
16     point[size]=b;
17     nxt[size]=head[a];
18     head[a]=size++;
19 }
20 
21 bool dfs(int s){
22     vis[s]=-1;
23     for(int i=head[s];~i;i=nxt[i]){
24         int j=point[i];
25         if(vis[j]==-1)return 0;
26         if(!vis[j]&&!dfs(j))return 0;
27     }
28     vis[s]=1;
29     topo[t--]=s;
30     return 1;
31 }
32 
33 bool toposort(int n){
34     t=n;
35     memset(vis,0,sizeof(vis));
36     for(int i=1;i<=n;++i){
37         if(!vis[i]){
38             if(!dfs(i))return 0;
39         }
40     }
41     return 1;
42 }

接下来是BFS实现的，一般用队列就可以满足需要了，如果要求字典序最小，可以改成优先队列实现，但是只能输出一个排序。在过程中可以加入判断，每次从队列中取出元素删除后，判断队列是否为空，若任意一次不为空则可以说明拓扑序不唯一。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 
 6 const int maxn=1e5+5;
 7 const int maxm=1e5+5;
 8 
 9 int ans,n;
10 int head[maxn],point[maxm],nxt[maxm],size;
11 int id[maxn],num[maxn];
12 
13 void init(){
14     memset(head,-1,sizeof(head));
15     size=0;
16 }
17 
18 void add(int a,int b){
19     point[size]=b;
20     nxt[size]=head[a];
21     head[a]=size++;
22     id[b]++;
23 }
24 
25 bool topo(){
26     //  priority_queue<int,vector<int>,greater<int> >q;
27     queue<int>q;
28     for(int i=1;i<=n;++i)if(!id[i])q.push(i);
29     int cnt=0;
30     while(!q.empty()){
31         int u=q.front();q.pop();
32         cnt++;
33         for(int i=head[u];~i;i=nxt[i]){
34             int j=point[i];
35             id[j]--;
36             if(!id[j])q.push(j);
37         }
38     }
39     if(cnt==n)return 1;
40     return 0;
41 }

然后是DFS版，可以实现输出所有拓扑序的输出，并且通过进入DFS的顺序的控制也基本能实现字典序输出。

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 const int maxn=1e5+5;
 5 const int maxm=1e5+5;
 6 
 7 int head[maxn],point[maxm],nxt[maxm],size;
 8 int ma[maxm][maxm],id[maxm],n,vis[maxm],v[maxm];
 9 int ans[maxm];
10 
11 void init(){
12     memset(head,-1,sizeof(head));
13     size=0;
14 }
15 
16 void add(int a,int b){
17     point[size]=b;
18     nxt[size]=head[a];
19     head[a]=size++;
20     id[b]++;
21 }
22 
23 void dfs(int s,int t){
24     ans[t]=s;
25     v[s]=1;
26     if(t==n){
27         for(int i=1;i<=n;++i){
28             printf("%d",ans[i]);
29             if(i==n)printf("\n");
30             else printf(" ");
31         }
32         v[s]=0;
33         return;
34     }
35     int que[maxn],cnt=0;
36     for(int i=1;i<=n;++i){
37         if(ma[s][i])id[i]--;
38         if(vis[i]&&!id[i]&&!v[i])que[++cnt]=i;
39     }
40     for(int i=1;i<=cnt;++i)dfs(que[i],t+1);
41     for(int i=1;i<=n;++i)if(ma[s][i])id[i]++;
42     v[s]=0;
43 }
44 
45 for(int i=1;i<=n;++i){
46     if(vis[i]&&!id[i])dfs(i,1);
47 }

1、拓扑排序的介绍

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。 
拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。 
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

2、拓扑排序的实现步骤

1. 在有向图中选一个没有前驱的顶点并且输出
2. 从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）
3. 重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。

3、拓扑排序示例手动实现

如果我们有如下的一个有向无环图，我们需要对这个图的顶点进行拓扑排序，过程如下： 

首先，我们发现V6和v1是没有前驱的，所以我们就随机选去一个输出，我们先输出V6，删除和V6有关的边，得到如下图结果： 

然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果： 

然后，我们又发现V4和V3都是没有前驱的，那么我们就随机选取一个顶点输出（具体看你实现的算法和图存储结构），我们输出V4，得到如下图结果： 

然后，我们输出没有前驱的顶点V3，得到如下结果： 

然后，我们分别输出V5和V2，最后全部顶点输出完成，该图的一个拓扑序列为：

v6–>v1—->v4—>v3—>v5—>v2

4、拓扑排序的代码实现

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int maxn=100;
bool g[maxn][maxn];
bool vis[maxn];
int inx[maxn];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(vis,false,sizeof(vis));
    memset(g,0,sizeof(g));
    memset(inx,0,sizeof(inx));
    for(int i=0;i<m;i++){
        int from ,to;
        scanf("%d%d",&from, &to);
        if(!g[from][to]){
            g[from][to]=true;
            inx[to]++;
        }
    }
    queue<int > que;
    for(int i=0;i<n;i++){
        if(!inx[i]){
            que.push(i);
            vis[i]=true;
        }
    }
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int i=0;i<n;i++){
            if(g[u][i]&&!vis[i])inx[i]--;
        }
        for(int i=0;i<n;i++){
            if(!inx[i]&&!vis[i]){
                que.push(i);
                vis[i]=true;
            }
        }
        cout<<u<<' ';
    }
    cout<<endl;
    return 0;
}

1

1

ACM-图论-拓扑排序

拓扑排序用于解决图论中有向图的一类序列问题。即在某一个有向图graph中，假设每一条有向边(u,v)代表节点u必须排在节点v的前面，那么按照这样的规则，将所有的节点进行排序，最终得出的序列就称为拓扑序。拓扑排序在ACM比赛和实际生活中都比较常见，只要能将事物抽象成有向图，并要求按规则排序，那么就可以考虑拓扑排序，比如选修课程的安排、按胜负排名次等。

拓扑排序只适用于有向无环图，所以使用拓扑排序的第一步就是先将问题抽象成有向图，进行图的初始化、建立等工作，然后运行拓扑排序算法即可。

然后考虑如何实现拓扑排序。按照其原始的定义，边(u,v)代表u排在v前面，也就是说没有边指向的节点拓扑序较小，所以拓扑序为1的节点应该是入度为0的点，再考虑拓扑序为2的节点，它最多只应该是拓扑序唯一指向的节点，而不能由其它节点指向它，否则它的拓扑序不为2，那这样看来该节点不就是删除以拓扑序为1的节点出发的边后，入度为0的节点了么。综上，拓扑排序算法的大题思路就是：每次选出入度为0的节点，然后删除该节点以及由该节点出发的边，调整其它节点的入度，然后再选出入度为0的节点，相同的处理方法，依次类推，直到没有入度为0的节点为止。那么，每次选出节点的顺序就是拓扑序。

最后考虑一下细节，如果图用邻接表来存储的话，那么入度信息就可以使用第一个元素维护，并且重边对拓扑序无影响，因为删除节点的时候同样会删除重边，还有就是拓扑排序运行的最终结果就是为每一个节点都分配了拓扑序号，所有节点维护的入度信息都被更新为了0，否则说明图中存在环。

这里有一道关于拓扑排序的常见应用的题，HDOJ：1285，时空转移(点击打开链接)，题目如下：

确定比赛名次

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16595    Accepted Submission(s): 6566

Problem Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3 1 2 2 3 4 3

Sample Output

1 2 4 3

题意：

给出比赛的输赢结果，要求赢得排在输的前面，然后要求以此对所有的队伍进行排序。

分析：

可以讲队伍看成节点，然后将输赢看成节点间的一条边，这样就将问题抽象成了图，那么问题就转化成了拓扑排序。

源代码：

1. #include <cstdio>  

   #include <vector>  

   #include <queue>  

   #include <algorithm>  

     

   using namespace std;  

   const int MAXN = 505;  

   vector<int> Graph[MAXN];  

   int TopNum[MAXN], NodeNum[MAXN];;  

   int NumVertex, NumEdge;  

     

   // 有向无环图一定存在拓扑序  

   void TopSort()  

   {  

       // 维护入度为0的节点，编号从小到大排序，保证编号小的节点的拓扑序小  

       priority_queue<int, vector<int>, greater<int> > que;  

       // 将入度为0的节点加入队列  

       for(int i=1; i<=NumVertex; ++i)  

       {  

           if(Graph[i][0] == 0) que.push(i);  

       }  

       // 循环处理入度为0的节点，并赋予拓扑序  

       int cnt = 0;  

       while(!que.empty())  

       {  

           int u = que.top();  

           que.pop();  

           // 将最较小拓扑序号赋给入度为0且当前编号最小的节点  

           TopNum[u] = ++cnt;  

           // 删除节点u出发的边，并调整其它节点的入度  

           for(int i=1; i<Graph[u].size(); ++i)  

           {  

               // 将调整后入度为0的节点加入队列  

               if(--Graph[Graph[u][i]][0] == 0) que.push(Graph[u][i]);  

           }  

       }  

       // 图中存在环则无拓扑序  

       if(cnt != NumVertex) return;  

       // 如果图并不一定是全联通的，那么判原图的某一连通域中是否存在环：  

       for(int i=1; i<=NumVertex; ++i) if(Graph[i][0]) puts("somerwhere of the graph has a cycle");  

     

       // 输出以拓扑序排列的节点编号  

       for(int i=1; i<=NumVertex; ++i) NodeNum[TopNum[i]] = i;  

       for(int i=1; i<=NumVertex; ++i) printf("%d%c", NodeNum[i], i==NumVertex?'\n':' ');  

   }  

     

   int main()  

   {//freopen("sample.txt", "r", stdin);  

       while(~scanf("%d%d", &NumVertex, &NumEdge))  

       {  

           // 初始化  

           for(int i=1; i<=NumVertex; ++i)  

           {  

               Graph[i].clear();  

               // 初始化入度  

               Graph[i].push_back(0);  

           }  

           // 建图  

           for(int i=1; i<=NumEdge; ++i)  

           {  

               int u, v;  

               scanf("%d%d", &u, &v);  

               // 使用邻接表时，重边对于拓扑序无影响，所以可以不用处理  

               //if(find(Graph[u].begin(), Graph[u].end(), v)  

               //   == Graph[u].end())  

               {  

                   Graph[u].push_back(v);  

                   // v节点的入度加1  

                   ++Graph[v][0];  

               }  

           }  

           // 拓扑排序  

           TopSort();  

       }  

       return 0;  

   }  

   
   其它相关的题目还有，HDOJ：1811，UESTC：1150。