2011年8月8日 星期一

ACM 10305 Ordering Tasks

快一個月沒寫ACM感覺怪怪的@@"

這題是基本的Topological Sort,我完全照著演算法筆記的code打的= =+


#include <stdio.h>
#include <stdbool.h>
bool map[101][101];
int ref[101];
int main(void)
{
    int m, n, t, i, j, s, first;
   
    while (scanf("%d%d", &n, &m) == 2 && (m || n))
    {
        for (i = 1; i <= n; i++)
            ref[i] = 0;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                map[i][j] = false;
        for (t = 0; t < m; t++)
        {
            scanf("%d%d", &i, &j);
            map[i][j] = true;
            ref[j]++;
        }
        first = 1;
        for (t = 1; t <= n; t++)
        {
            s = 1;
            while (s <= n && ref[s] != 0)
                s++;
            ref[s] = -1;
            if (first)
            {
                printf("%d", s);
                first = 0;
            }
            else
            {
                printf(" %d", s);
            }
            for (j = 1; j <= n; j++)
                if (map[s][j])
                    ref[j]--;
        }
        puts("");
    }
    return 0;
}

沒有留言:

張貼留言