hdu 3342（拓撲排序）

拓撲排序，，水

2013-04-25

[cpp]
#include"stdio.h"  
#include"string.h"  
int cnt[101]; 
int map[101][101]; 
int topsort(int n) 
{ 
    int i,j,k; 
    k=0; 
    while(k<n) 
    { 
        for(i=0;i<n;i++) 
        { 
            if(cnt[i]==0) 
            { 
                cnt[i]--; 
                k++; 
                for(j=0;j<n;j++) 
                    if(map[i][j])cnt[j]--; 
                break; 
            } 
        } 
        if(i==n)return 0; 
    } 
    return 1; 
} 
 
int main() 
{ 
    int ans; 
    int n,m; 
    int i,a,b; 
    while(scanf("%d%d",&n,&m)!=-1,n||m) 
    { 
        memset(map,0,sizeof(map)); 
        memset(cnt,0,sizeof(cnt)); 
        for(i=0;i<m;i++) 
        { 
            scanf("%d%d",&a,&b); 
            if(map[a][b]==0) 
            { 
                map[a][b]=1; 
                cnt[b]++; 
            } 
        } 
        ans=topsort(n); 
        printf("%s\n",ans==1?"YES":"NO"); 
    } 
    return 0; 
} 
         

#include"stdio.h"
#include"string.h"
int cnt[101];
int map[101][101];
int topsort(int n)
{
 int i,j,k;
 k=0;
 while(k<n)
 {
  for(i=0;i<n;i++)
  {
   if(cnt[i]==0)
   {
    cnt[i]--;
    k++;
    for(j=0;j<n;j++)
     if(map[i][j])cnt[j]--;
    break;
   }
  }
  if(i==n)return 0;
 }
 return 1;
}

int main()
{
 int ans;
 int n,m;
 int i,a,b;
 while(scanf("%d%d",&n,&m)!=-1,n||m)
 {
  memset(map,0,sizeof(map));
  memset(cnt,0,sizeof(cnt));
  for(i=0;i<m;i++)
  {
   scanf("%d%d",&a,&b);
   if(map[a][b]==0)
   {
    map[a][b]=1;
    cnt[b]++;
   }
  }
  ans=topsort(n);
  printf("%s\n",ans==1?"YES":"NO");
 }
 return 0;
}