逃生

题目链接

• 分析：
  题目要求在满足拓扑的前提下。小序号须要先输出。能够先考虑1号节点。是1的父节点的一定是要在1的前边输出的，那么反向建边再反向输出答案肯定是满足拓扑关系的。想想为什么正向拓扑不行，由于对于1号节点，应该是最先考虑怎么把它输出的，可是假设正向拓扑就会考虑1号节点之前的点的优先顺序，比方1前边有一个最大值，那么1就成最后考虑的了。

const int maxn = 30010;

int d[maxn];
vector<int>v[maxn];
priority_queue<int, vector<int>, less<int> > q;
int n, m;
vector<int> ans;
int main ()
{
    int T;
    cin >> T;
    while (T--)
    {
        ans.clear();
        RII(n, m);
        CLR(d, 0);
        for (int i = 0; i <= n; i++) v[i].clear();
        for (int i = 0; i < m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            v[y].push_back(x);
            d[x]++;
        }
        for (int i = 1; i <= n; i++)
            if (!d[i])
                q.push(i);
        while (!q.empty())
        {
            int x = q.top(); q.pop();
            ans.push_back(x);
            for (int i = 0; i < v[x].size(); i++)
            {
                int y = v[x][i];
                if (--d[y] == 0)
                {
                    q.push(y);
                }
            }
        }
        FED(i, n - 1, 0)
            printf("%d%c", ans[i], i == 0 ? '
' : ' ');
    }
    return 0;
}