第六章拓扑排序

uva10305

深度优先用来找入度为零0的节点

 1 bool bfs(int u)
 2 {
 3     c[u]=-1;
 4 
 5     for(int i=1;i<=n;i++)
 6     {
 7         if(e[u][i])
 8         {
 9             if(c[i]<0) return false;
10             if(!c[i] && !bfs(i)) return false;
11         }
12     }
13 
14     c[u]=1;
15     store[--t]=u;
16     return true;
17 }

1.如果是有环的有向图则返回false 实现的代码为第九行

2.利用for循环来对节点间可能的联系进行判断,从而实现在边上移动.

拓扑排序

bool topsort()
{
    memset(c,0,sizeof(c));
    memset(store,0,sizeof(store));

    for(int i=1;i<=n;i++)
    {
        if(!c[i])
        {
            if(!bfs(i))
                return false;
        }
    }
    return true;
}

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=10000;
 8 int e[maxn][maxn];
 9 int c[maxn];
10 int store[maxn];
11 
12 int n,m,t;
13 
14 
15 /*深度优先用来找入度为零的节点*/
16 
17 bool bfs(int u)
18 {
19     c[u]=-1;
20 
21     for(int i=1;i<=n;i++)
22     {
23         if(e[u][i])
24         {
25             if(c[i]<0) return false;        //判断有没有环
26             if(!c[i] && !bfs(i)) return false;  //如果未被访问且访问后有环
27         }
28     }
29 
30     //该节点现在可以被看成入度为零的节点了
31     
32     c[u]=1;
33     store[--t]=u;
34     return true;
35 }
36 
37 
38 bool topsort()
39 {
40     memset(c,0,sizeof(c));
41     memset(store,0,sizeof(store));
42 
43     //从每个节点出发一次
44     
45     
46     for(int i=1;i<=n;i++)
47     {
48         if(!c[i])
49         {
50             if(!bfs(i))
51                 return false;
52         }
53     }
54     return true;
55 }
56 
57 int main()
58 {
59     while(scanf("%d%d",&n,&m)==2 && (m||n))
60     {
61         t=n;
62         memset(e,0,sizeof(e));
63 
64         for(int i=0;i<m;i++)
65         {
66             int k,p;
67             cin>>k>>p;
68 
69             e[k][p]=1;
70         }
71 
72         if(topsort())
73             for(int i=0;i<n;i++) 
74                 i==0? cout<<store[i]:cout<<" "<<store[i];
75         else cout<<"NO";
76 
77         cout<<endl;
78 
79     }
80     return 0;
81 }

Yosoro