数据结构实验之图论十：判断给定图是否存在合法拓扑序列

布满荆棘的人生 2022-04-11 14:38 159阅读 0赞

Problem Description

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input

输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

Output

若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

Sample Input

1 0  
2 2  
1 2  
2 1

Sample Output

YES  
NO

此题意思就是判断有没有回路，方法就是逐个删删除点（入度为0）

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int map[100][100];//存图
    int   v[100];//标记是否遍历过
    int   d[100];//记录入度
    
    int main()
    {
       int n,m;
       while(scanf("%d %d",&n,&m)!=EOF)
       {
           int i,j,k;
           int a,b;
           memset(map,0,sizeof(map));
           memset(v,0,sizeof(v));
           memset(d,0,sizeof(d));//三个初始化
           while(m--)
           {
               scanf("%d %d",&a,&b);
               map[a][b]=1;
               d[b]++;
           }//构造单向图，并且标记好每个点的入度
           int count=n;//记录还有多少个点
           for(i=1;i<=n;i++)//对于每个点都要进行遍历，删掉n次
           {
               for(j=1;j<=n;j++)//对于一个点遍历其他的点
               {
                   if(d[j]==0&&v[j]==0)//如果找到一个点度数为0，且没有被遍历过
                   {
                       v[j]=1;//标记成遍历过
                       count--;//数量减少
                       for(k=1;k<=n;k++)//与该点相邻的点的度数减少
                       {
                           if(map[j][k]==1)
                           {
                               d[k]--;
                           }
                       }
                   }
               }
           }
           if(count==0)//如果所有的点都被删除
            printf("YES\n");
           else
            printf("NO\n");
       }
        return 0;
    }