一道拓补排序的题,虽然a了但是是看题解过的......存在的疑问已在注释中标明
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int gra[205][205];
int deg[40005]; //记录入度
int ans[40005];
int n,m;
bool topo()
{
int tag;int cnt=0;
for(int i=n;i>=1;i--){ //这样反向循环的原理到底是什么?
for(int j=n;j>=1;j--){
if(deg[j]==0){
tag=j;
deg[j]--;
ans[j]=i; //???
cnt++;
break;
}
}
for(int j=1;j<=n;j++){
if(gra[tag][j]>0)
deg[j]--;
}
}
if(cnt<n)
return false;
return true;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
mst(deg,0);mst(gra,0);mst(ans,0);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
if(!gra[b][a]) //???这里删去以后就会RE
deg[a]++;
gra[b][a]=1; //为什么要反向建图???
}
if(!topo())
cout<<-1<<endl;
else{
int pr=0;
for(int i=1;i<=n;i++){
if(!pr)
printf("%d",ans[i]);
else
printf(" %d",ans[i]);
pr++;
}
printf("\n");
}
}
return 0;
}