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

秒速五厘米 2022-08-10 06:11 178阅读 0赞

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

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

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

## 输入 ##

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

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

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

## 输出 ##

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

## 示例输入 ##

1 0
    2 2
    1 2
    2 1

## 示例输出 ##

YES
    NO

## 提示 ##

## 来源 ##

赵利强

## 示例程序 ##

#include<stdio.h>    
    #include<string.h>    
    int map[20][20],in[20];    
    int n;    
    void topo()    
    {    
    int i,j,k,l;    
    for(i=1;i<=n;i++)    
    {    
    k=0;    
    for(j=1;j<=n;j++)    
    if(in[j]==0)    
    {    
    k=1;    
    in[j]=-1;    
    for(l=1;l<=n;l++)    
    if(map[j][l])    
    in[l]--;    
    break;    
    }    
    if(k==0)    
    break;    
    }    
    if(k==0)    
    printf("NO\n");    
    else    
    printf("YES\n");    
    }    
    int main()    
    {    
    int i,j,m,k,t;    
    while(scanf("%d %d",&n,&m)!=EOF)    
    {    
    memset(map,0,sizeof(map));\    
    memset(in,0,sizeof(in));    
    while(m--)    
    {    
    scanf("%d %d",&i,&j);    
    map[i][j]=1;    
    in[j]++;    
    }    
    topo();    
    }    
    }