想到了一个分治方法，每一次尽量放小的那个，把它依赖的放在左边，不依赖的放在右边。
TLE 80：
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define pb push_back
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//*********************************** const int maxn = ; vector <int> Vx[maxn], Vy[maxn];
int src[maxn], lft[maxn]; int n, m;
int deg[maxn], tmp[maxn]; bool topo() {
static int que[maxn]; int qh(), qt();
rep(i, , n) if (!deg[i]) que[++qt] = i;
int cnt();
while (qh != qt) {
int x = que[++qh];
++cnt;
int len = (int) Vx[x].size();
for (int i = ; i < len; i++) {
if (--deg[Vx[x][i]] == ) que[++qt] = Vx[x][i];
}
}
return cnt == n;
} bool vis[maxn];
void bfs(int s) {
static int que[maxn]; int qh(), qt();
vis[que[++qt] = s] = ;
while (qh != qt) {
int x = que[++qh];
int len = (int) Vy[x].size();
for (int i = ; i < len; i++) {
if (!vis[Vy[x][i]]) {
vis[que[++qt] = Vy[x][i]] = ;
lft[Vy[x][i]] = ;
}
}
}
} void solve(int l, int r) {
if (l >= r) return;
int t, haha = inf;
rep(i, l, r) if (src[i] < haha) { t = i; haha = src[i]; }
rep(i, l, r) lft[src[i]] = vis[src[i]] = ;
bfs(src[t]);
int cur = l - ;
rep(i, l, r) if (src[i] != src[t] && lft[src[i]]) tmp[++cur] = src[i];
tmp[++cur] = src[t]; int mid = cur;
rep(i, l, r) if (src[i] != src[t] && !lft[src[i]]) tmp[++cur] = src[i];
memcpy(src + l, tmp + l, sizeof(int) * (r - l + ));
solve(l, mid - );
solve(mid + , r);
} int main() {
freopen("dishes.in", "r", stdin);
freopen("dishes.out", "w", stdout);
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
rep(i, , n) Vx[i].clear(), Vy[i].clear();
clr(deg);
rep(i, , m) {
int x, y; scanf("%d%d", &x, &y);
Vx[x].pb(y);
Vy[y].pb(x);
deg[y]++;
}
if (!topo()) { puts("Impossible!"); continue; }
rep(i, , n) src[i] = i;
solve(, n);
rep(i, , n) printf(i == n ? "%d\n" : "%d ", src[i]);
}
return ;
}
正解：
有依赖关系，我们建立反图，加入我们的到了这个反图的一个拓扑序，那么怎样对应到最优的答案呢？应该是尽量让编号小的出现在队列后方，所以最大字典序的拓扑排序即可。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define pb push_back
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//*********************************** const int maxn = ; vector <int> Vx[maxn], Vy[maxn];
priority_queue<int> Q;
int deg[maxn], ans[maxn], n, m; bool topo() {
rep(i, , n) if (!deg[i]) Q.push(i);
int cnt();
while (!Q.empty()) {
int x = Q.top(); Q.pop();
ans[++cnt] = x;
int len = (int) Vy[x].size();
for (int i = ; i < len; i++) {
if (--deg[Vy[x][i]] == ) Q.push(Vy[x][i]);
}
}
return cnt == n;
} int main() {
freopen("dishes.in", "r", stdin);
freopen("dishes.out", "w", stdout);
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
rep(i, , n) Vx[i].clear(), Vy[i].clear();
clr(deg);
rep(i, , m) {
int x, y; scanf("%d%d", &x, &y);
Vx[x].pb(y);
Vy[y].pb(x);
deg[x]++;
}
if (!topo()) puts("Impossible!");
else { drep(i, n, ) printf("%d ", ans[i]); puts(""); }
}
return ;
}