MENU

洛谷P3243/BZOJ4010/COGS1958 [HNOI2015]菜肴制作

洛谷P3243

BZOJ4010

COGS1958

建反图求最大字典序拓补序,反向输出。

内存泄露1/1

#include<bits/stdc++.h>
using namespace std;
int T, n, m, indgr[100001], topo[100001], cnt;
struct Edge {
    int to;
    Edge *nxt;
    Edge(int t, Edge *n) :to(t), nxt(n) {}
}*head[100001];
priority_queue<int>pq;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cin >> T;
    while (T--) {
        cin >> n >> m, memset(head, 0, sizeof head), cnt = 0, memset(indgr, 0, sizeof indgr);
        for (int i = 1, u, v; i <= m; i++)cin >> u >> v, head[v] = new Edge(u, head[v]), indgr[u]++;
        for (int i = 1; i <= n; i++)if (!indgr[i])pq.push(i);
        while (!pq.empty()) {
            topo[++cnt] = pq.top(), pq.pop();
            for (Edge *i = head[topo[cnt]]; i; i = i->nxt) {
                int vs = i->to;
                if (--indgr[vs]) continue;
                pq.push(vs);
            }
        }
        if (cnt < n) { cout << "Impossible!\n"; continue; }
        for (int i = n; i; i--)cout << topo[i] << ' ';
        cout << '\n';
    }
}