如何求拓扑排序的所有种类及种类数

输入：第一行为点数n和各连接边数m

　　　接下来m行写某一条有向边的起始点和终止点

输出：拓扑排序所有方案和方案种数

sample input

sample output

0 1 3 2 8 6 7 5 4
0 1 3 2 8 7 6 5 4
0 1 3 8 2 6 7 5 4
0 1 3 8 2 7 6 5 4
0 1 3 8 6 2 7 5 4
0 1 3 8 6 7 2 5 4
0 1 3 8 6 7 5 2 4
0 1 3 8 7 2 6 5 4
0 1 3 8 7 6 2 5 4
0 1 3 8 7 6 5 2 4
0 1 8 3 2 6 7 5 4
0 1 8 3 2 7 6 5 4
0 1 8 3 6 2 7 5 4
0 1 8 3 6 7 2 5 4
0 1 8 3 6 7 5 2 4
0 1 8 3 7 2 6 5 4
0 1 8 3 7 6 2 5 4
0 1 8 3 7 6 5 2 4
0 1 8 7 3 2 6 5 4
0 1 8 7 3 6 2 5 4
0 1 8 7 3 6 5 2 4
0 8 1 3 2 6 7 5 4
0 8 1 3 2 7 6 5 4
0 8 1 3 6 2 7 5 4
0 8 1 3 6 7 2 5 4
0 8 1 3 6 7 5 2 4
0 8 1 3 7 2 6 5 4
0 8 1 3 7 6 2 5 4
0 8 1 3 7 6 5 2 4
0 8 1 7 3 2 6 5 4
0 8 1 7 3 6 2 5 4
0 8 1 7 3 6 5 2 4
0 8 7 1 3 2 6 5 4
0 8 7 1 3 6 2 5 4
0 8 7 1 3 6 5 2 4
8 0 1 3 2 6 7 5 4
8 0 1 3 2 7 6 5 4
8 0 1 3 6 2 7 5 4
8 0 1 3 6 7 2 5 4
8 0 1 3 6 7 5 2 4
8 0 1 3 7 2 6 5 4
8 0 1 3 7 6 2 5 4
8 0 1 3 7 6 5 2 4
8 0 1 7 3 2 6 5 4
8 0 1 7 3 6 2 5 4
8 0 1 7 3 6 5 2 4
8 0 7 1 3 2 6 5 4
8 0 7 1 3 6 2 5 4
8 0 7 1 3 6 5 2 4
8 7 0 1 3 2 6 5 4
8 7 0 1 3 6 2 5 4
8 7 0 1 3 6 5 2 4
sum:52

代码：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 int n,m;
 6 int s[100][100];        //邻接矩阵，用于保存图的结构 
 7 int visit[100];        //顶点标志 
 8 int indegree[100];        //各个顶点的入度 
 9 int ans[100];
10 int sum=0;            //记录拓扑排序总数 
11 void DFS(int num)        //num记录当前已经访问的顶点个数 
12 {
13     int i,j,k;
14     if (num==n){        //访问完n个顶点代表这是一条新的可走的拓扑路径 
15         sum++;             //路径总数加1 
16         for (i=0;i<n;i++)
17             printf("%d ",ans[i]);
18         printf("
");
19         return;
20     } 
21     
22     for (i=0;i<n;i++){
23         if ((!indegree[i])&&(!visit[i])){        //如果顶点i入度为0且没有被访问过 
24             for (j=0;j<n;j++){
25                 if (s[i][j])    indegree[j]--;    //遍历所有和它连接的点并且断开联系（即点的入度减1） 
26             }
27             
28             visit[i]=1;            //该入度为0的点标记访问过 
29             ans[num]=i;            //储存值 
30             DFS(num+1);            //以访问点数+1 
31             
32             for (k=0;k<n;k++){    //回溯，恢复现场，将入度重新加一，并且将该顶点标记为未访问
33                 if (s[i][k])    indegree[k]++;
34             }
35             visit[i]=0;            //回溯标志 方便下一次for循环使用 
36                                 //ans没有必要回溯，因为后续的值可以直接覆盖 
37         }
38     }
39     return;
40 }
41  
42 int main(){
43     int a,b,i,j,num;
44     scanf("%d%d",&n,&m);
45     memset(indegree,0,sizeof(indegree));
46     memset(s,0,sizeof(s));
47     memset(visit,0,sizeof(visit));
48     memset(ans,0,sizeof(ans));
49     
50     for (i=1;i<=m;i++){
51          scanf("%d%d",&a,&b);
52         s[a][b]=1;
53         indegree[b]++;
54      } 
55  
56     DFS(0);
57     cout<<"sum:"<<sum;
58     return  0;
59 }