1 #include<iostream>
 2 #include<stdlib.h>
 3 #include<stdio.h>
 4 #define MAX 100
 5 using namespace std;
 6 
 7 void toposort(int map[MAX][MAX],int indegree[MAX],int n)
 8 {
 9     int i,j,k;
10     for(i=0;i<n;i++)           //遍历n次
11     {
12         for(j=0;j<n;j++)      //找出入度为0的节点
13          {
14             if(indegree[j]==0)
15             {
16                 indegree[j]--;
17                 cout<<j<<endl;
18                 for(k=0;k<n;k++)    //删除与该节点关联的边
19                   {
20                     if(map[j][k]==1)
21                     {
22                         indegree[k]--;
23                     }
24                 }
25                 break;
26             }
27         }
28     }
29 }
30 
31 
32 int main(void)
33 {
34     int n,m;           //n:关联的边数，m:节点数
35     while(scanf("%d %d",&n,&m)==2&&n!=0)
36     {
37         int i;
38         int x,y;
39         int map[MAX][MAX];//邻接矩阵
40         int indegree[MAX];//入度
41         memset(map,0,sizeof(map));
42         memset(indegree,0,sizeof(indegree));
43         for(i=0;i<n;i++)
44         {
45             scanf("%d %d",&x,&y);
46             if(!map[x][y])//防止入度重复加 
47             {
48                 map[x][y]=1;
49                 indegree[y]++;
50             }
51         }
52         toposort(map,indegree,m);
53     }
54     //while(1);
55     return 0;
56 }
57 
58 
59 //http://www.cnblogs.com/dolphin0520/archive/2011/04/16/2017737.html

　　2.递归实现

 1 int c[maxn];
 2 int topo[maxn],t;
 3 
 4 bool dfs(int u)
 5 {
 6    c[u]=-1;//正在访问该顶点
 7    for(int v=0; v<n; v++)
 8    {
 9        if(G[u][v]==1)
10        {
11             if(c[v]<0) return false;//存在环   
12             //c[v]=-1代表正在访问该定点（即递归调用dfs(u)正在帧栈中，尚未返回）
13             else if(!c[v] && !dfs(v))   return false;   
14             //（c[v]==0 && dfs(v)==false即当前顶点没有后继顶点时
15 
16        }
17    }
18 
19    c[u]=1;      //访问结束
20    topo[--t]=u;
21    return true;
22 }
23 
24 bool toposort()
25 {
26     t=n;    
27     memset(c,0,sizeof(c));
28         
29     for(int u=0; u<n; u++)    
30         if(!c[u]) 
31             if(!dfs())  
32                 return false;    
33     return ture;
34 }

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。