hdu 3342 Legal or Not（给一个有向图判断该图是否拓扑有序）

#include<cstdio>
#include<cstring>
using namespace std;

int n,m;
int mat[105][105];
int in[105];
int Stack[105],top;

void topo()
{
    top=0;
    for(int i=0; i<n; i++)
    {
        if(in[i]==0)
        {
            Stack[++top]=i;
            in[i]=-1;
        }
    }
    int cnt=0;
    while(top!=0)
    {
        int j=Stack[top--];
        cnt++;
        for(int i=0; i<n; i++)
        {
            if(mat[j][i])
            {
                in[i]-=(mat[j][i]);
            }
            if(in[i]==0)
            {
                Stack[++top]=i;
                in[i]=-1;
            }
        }
    }
    if(cnt==n)
        printf("YES\n");
    else
        printf("NO\n");
}

int main()
{
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        memset(mat,0,sizeof(mat));
        memset(in,0,sizeof(in));
        for(int i=0; i<m; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            mat[a][b]++;
            in[b]++;
        }
        topo();
    }
    return 0;
}

hdu 3342 Legal or Not（给一个有向图判断该图是否拓扑有序）

原文：http://blog.csdn.net/xky1306102chenhong/article/details/47207429