图结构练习——判断给定图是否存在合法拓扑序列

就是判断有向图中是否有环由于开始用dfs搜忘记return了纠结了一下午还是经虎学长指点才找到错误

递归

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int g[101][101],c[101];
 4 int dfs(int u,int n)
 5 {
 6     int v;
 7     c[u] = -1;
 8     for(v = 1 ; v <= n ; v++)
 9         if(g[u][v])
10         {
11             if(c[v]<0)
12             {
13                 return 0;
14             }
15             else
16                 if(!c[v]&&!dfs(v,n))
17                     return 0;
18         }
19     c[u] = 1;
20     return 1;
21 }
22 int toposort(int n)
23 {
24     int u;
25     memset(c,0,sizeof(c));
26     for(u = 1 ;u <= n ;u++)
27         if(!c[u])
28         {
29             if(!dfs(u,n))
30                 return 0;
31         }
32     return 1;
33 }
34 int main()
35 {
36     int n,m,i,j,a,b;
37     while(scanf("%d%d", &n,&m)!=EOF)
38     {
39         memset(g,0,sizeof(g));
40         for(i = 1 ;i <= m ; i++)
41         {
42             scanf("%d%d",&a,&b);
43             g[a][b] = 1;
44         }
45         if(toposort(n))
46             printf("YES\n");
47         else
48             printf("NO\n");
49     }
50     return 0;
51 }

拓扑排序非递归
若有环最后肯定找不到n个入度为0的节点

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int de[101],g[101][101],flag;
 4 void topo(int n)
 5 {
 6     int i,j,k,w = 0;
 7     for(i = 1 ; i <= n ; i++)
 8     {
 9         w = 0;
10         for(j = 1 ;j <= n ;j++)
11         {
12             if(de[j]==0)
13             {    w = 1;
14                 de[j]--;
15                 for(k = 1 ; k <= n ; k++)
16                     if(g[j][k])
17                         de[k]--;
18                 break;
19             }
20         }
21         if(!w)
22         {
23             flag = 0;
24             break;
25         }
26     }
27 }
28 int main()
29 {
30     int i,j,k,m,n,a,b;
31     while(scanf("%d%d", &n,&m)!=EOF)
32     {
33         memset(de,0,sizeof(de));
34         memset(g,0,sizeof(g));
35         flag = 1;
36         for(i =1 ;i <= m ;i++)
37         {
38             scanf("%d%d", &a,&b);
39             g[a][b] = 1;
40             de[b]++;
41         }
42         topo(n);
43         if(flag)
44             printf("YES\n");
45         else
46             printf("NO\n");
47     }
48     return 0;
49 }