sicily1940. Ordering Tasks

1940. Ordering Tasks

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

 John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

 

Input

There are multiple test cases. The first line contains an integer T, indicating the number of test cases. Each test case begins with a line containing two integers, 1 <= n <= 100000 and 1 <= m <= 100000. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. It is guaranteed that no task needs to be executed before itself either directly or indirectly. 

 

Output

For each test case, print a line with n integers representing the tasks in a possible order of execution. To separate them, print exactly one space after each integer. If there are multiple solutions, output the smallest one by lexical order.  

 

Sample Input

1
5 5
3 4
4 1
3 2
2 4
5 3 

 

Sample Output

5 3 2 4 1 

 

题目分析：

这是一道典型的拓扑排序的题目。可以按照题目要求，把拓扑图建立好，然后一次宽度搜索就可以完成。

 

题目链接：

http://soj.me/1940

 

参考代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <stdio.h>
using namespace std;

const int N = 100009;

int main()
{
    int t;
    scanf("%d", &t);
    int m, n;
    int f, s;
    while (t --)
    {
        scanf("%d%d", &m, &n);
        multiset<int> v[N];
        int dev[N];
        memset(dev, 0, sizeof(dev));
        for (int i = 1; i <= n; ++ i)
        {
            scanf("%d%d", &f, &s);
            v[f].insert(s);
            ++ dev[s];
        }
        set<int> q;
        for (int i = 1; i <= m; ++ i)
        {
            if (dev[i] == 0)
            {
                q.insert(i);
            }
        }
        int count = 0;
        while (!q.empty())
        {
            set<int>::iterator itt = q.begin();
            int tem = *itt;
            if (count == 0)
            {
                printf("%d ", tem);
                ++ count;
            }
            else
            {
                printf("%d ", tem);
            }
            q.erase(itt);
            multiset<int>::iterator it = v[tem].begin();
            for (; it != v[tem].end(); it ++)
            {
                dev[*it] --;
                if (dev[*it] == 0)
                {
                    q.insert(*it);
                }
            }
        }
        printf("\n");
    }
}