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

范范 2019-11-02

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int map[100][100],visited[100],du[100],flag,n,m,i,j,k;
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        memset(map,0,sizeof(map));
        memset(visited,0,sizeof(visited));
        memset(du,0,sizeof(du));
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            map[a][b]=1;
            du[b]++;
        }
        for(i=1; i<=n; i++)
        {
            flag=0;
            for(j=1; j<=n; j++)
            {
                if(visited[j]==0&&du[j]==0)
                {
                    visited[j]=1;
                    for(k=1; k<=n; k++)
                    {
                        if(map[j][k]==1)
                            du[k]--;
                    }
                    flag=1;
                    break;
                }
            }
        }
        if(flag==1)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

相关推荐