大意略。
思路:把指向关系变一下,即A->B代表A重量一定比B重要要大。然后拓扑时,从编号最大的开始寻找即可。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <map> using namespace std; const int maxn = 210; const int maxm = 210*210; const int INF = 0x3f3f3f3f; int cnt; int first[maxn]; int topo[maxn]; int ind[maxn]; struct Edge { int u, v; int next; }edge[maxm]; void init() { cnt = 0; memset(first, -1, sizeof(first)); memset(ind, 0, sizeof(ind)); } void read_graph(int u, int v) { edge[cnt].u = u, edge[cnt].v = v; edge[cnt].next = first[u], first[u] = cnt++; } inline void readint(int &x) { char c = getchar(); while(!isdigit(c)) c = getchar(); x = 0; while(isdigit(c)) { x = x*10 + c-'0'; c = getchar(); } } inline void writeint(int x) { if(x > 9) writeint(x/10); putchar(x%10+'0'); } int n, m; void read_case() { init(); readint(n), readint(m); for(int i = 0; i < m; i++) { int u, v; readint(u), readint(v); read_graph(v, u); ind[u]++; } } int toposort() { for(int i = 1; i <= n; i++) { int c = 0, u; for(int j = n; j >= 1; j--) if(!ind[j]) { c++; u = j; break; } if(c == 0) return -1; topo[i] = u; ind[u] = -1; for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v; ind[v]--; } } return 1; } int weight[maxn]; void solve() { read_case(); int ans = toposort(); if(ans == -1) { printf("-1\n"); return; } for(int i = 1; i <= n; i++) { weight[topo[i]] = n-i+1; } int first = 1; for(int i = 1; i <= n; i++) { if(first) printf("%d", weight[i]), first = 0; else printf(" %d", weight[i]); } printf("\n"); } int main() { int T; readint(T); while(T--) { solve(); } return 0; }