SDUT-2140_判断给定图是否存在合法拓扑序列

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

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 <string.h>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int n;/*n节点数量*/

int f[1050];/*记录点是否被遍历过*/

int INF = 1e9+7;/*相当于无穷大*/

int s[1050][1050];

int c[1050],r[1050];/*记录节点的出度，入度*/

int main()

{

    int m,i,j,num;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        num = 0;

        for(i=1;i<=n;i++)

        {

            c[i] = r[i] = 0;

            f[i] = 0;

            for(j=1;j<=n;j++)

                s[i][j] = 0;

        }

        for(i=1;i<=m;i++)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            c[a]++;

            r[b]++;

            s[a][b] = 1;

        }

        for(int l=0;l<n;l++)

        {

            for(i=1;i<=n;i++)

            {

                if(!f[i]&&r[i]==0)/*点的入度为0且没有被遍历过，标记并且遍历与他有关的边，删除*/

                {

                    f[i] = 1;

                    for(j=1;j<=n;j++)

                    {

                        if(s[i][j])

                            r[j]--;

                    }

                    num++;

                    break;

                }

            }

        }

        if(num==n)

            printf("YES\n");

        else

            printf("NO\n");

    }

    return 0;

}

巴特西