判断给定图是否存在合法拓扑序列

左手的ㄟ右手 2023-06-15 14:26 1阅读 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

#include<stdio.h>
    #include<string.h>
    
    int mp[100][100];
    int vis[100];
    int in[100];
    int n,m;
    int flag;
    
    void Topsort()
    { 
        int i,j,k;
        for(j=1; j<=n; j++)
        { 
            if(vis[j]==0&&in[j]==0)
            { 
                flag++;
                vis[j]=1;
                for(k=1; k<=n; k++)
                { 
                    if(mp[j][k]==1)
                    { 
                        in[k]--;
                    }
                }
            }
        }
    }
    
    int main()
    { 
        int i;
        while(scanf("%d %d",&n,&m)!=EOF)
        { 
            flag=0;
            memset(mp,0,sizeof(mp));
            memset(vis,0,sizeof(vis));
            memset(in,0,sizeof(in));
            int a,b;
            for(i=1; i<=m; i++)
            { 
                scanf("%d %d",&a,&b) ;
                mp[a][b]=1;
                in[b]++;
            }
            Topsort();
            if(flag==n)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }