HDU 1285

题目 ：：点击打开链接

注意：拓扑排序，比较典型。

#include<stdio.h>
#include<string.h>

# define MAXN  501
int map[MAXN][MAXN];
int in_degree[MAXN];
int ans[MAXN], k, i, j;

void topo(int n)
{
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++){
           if(map[i][j])
               in_degree[j]++;
       }
    for(i=1; i<=n; i++)
    {
        k = 1;
        while(in_degree[k]!=0)
            k++;
        ans[i] = k;

        in_degree[k] = -1;
        for(j=1; j<=n; j++)
            if(map[k][j]!=0)
                in_degree[j]--;
    }

}

int main()
{
    int n, m, i, x, y;
    while(scanf("%d %d", &n, &m)!=EOF)
    {
         memset(map, 0, sizeof(map));
         memset(in_degree, 0, sizeof(in_degree));
         memset(ans, 0, sizeof(ans));

         for(i=1; i<=m; i++)
         {
             scanf("%d %d", &x, &y);
             map[x][y] = 1;
         }
         topo(n);

         for(i=1; i<n; i++)
         {
             printf("%d ", ans[i]);
         }
         printf("%d
", ans[n]);
    }
    return 0;
}