首页 > 代码库 > hdu 3342 Legal or Not (拓扑排序)

hdu 3342 Legal or Not (拓扑排序)

重边这样的东西   仅仅能呵呵

就是裸裸的拓扑排序

假设恩可以排出来就YES 。

else  NO

仅仅须要所有搜一遍就好了

#include <cstdio>
#include <cstring>
int mapp[101][101];
int d[101];
int n,m;
int a,b;
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0)break;
    	memset(d,0,sizeof(d));
    	memset(mapp,0,sizeof(mapp));
    	for(int i=0;i<m;i++){
    		scanf("%d%d",&a,&b);
    		if(!mapp[a][b])d[b]++;
    		mapp[a][b]=1;
    	}
    	int flag=1;
    	for(int i=0;i<n;i++){
    		int j;
    		for(j=0;j<n;j++){
    		if(d[j]==0){
    			d[j]--;
                for(int k=0;k<n;k++)
                if(mapp[j][k]){
                	d[k]--;
                }
                break;
    		}
    	}
    		if(j>=n)
    		{
                flag=0;
                break;
    		}
    	}
    	if(flag)puts("YES");
    	else puts("NO");
    }
}
/*又有重边,哈哈*/


hdu 3342 Legal or Not (拓扑排序)