题目描述
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.
输入描述
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.
输出描述
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.
输入样例
1
5 5
3 4
4 1
3 2
2 4
5 3
输出样例
5 3 2 4 1
Yizuodi的答案
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
const int MAX = 100001;
int main()
{
int times;//测试样例的数量
cin >> times;
while (times --)
{
int m, n;
cin >> m >> n;
multiset<int> E[MAX];
int in_degree[MAX];//某个节点的入度
memset(in_degree, 0, sizeof(in_degree));//初始化为0
for (int i = 1; i <= n; ++ i)
{
int a, b;
cin >> a >> b;//输入一条路径
E[a].insert(b);//
++ in_degree[b];//被指向的节点入度加1
}
set<int> q;//用于存储入度为0的节点
for (int i = 1; i <= m; ++ i)
{
if (in_degree[i] == 0)
{
q.insert(i);
}
}
while (!q.empty())//拓扑排序
{
int temp = *q.begin();
cout << *q.begin() << " ";
q.erase(*q.begin());
for (auto i = E[temp].begin(); i != E[temp].end(); i ++)//multiset<int>::iterator
{
in_degree[*i] --;
if (in_degree[*i] == 0)
{
q.insert(*i);
}
}
}
cout << endl;
}
}