//3696构造有向无环图

有向无环图才有拓扑排序，有环的话不能进行拓扑，因为会导致环中一个结点（环的入口位置）其入度永远无法变成0。

先判断图是否可拓扑序，如果本来就不能就直接No，可以的话。可以按照拓扑序。确定某个边的方向的时候，只要其起点拓扑序小于其终点即可。

要注意认真：YES格式写错了看了半天；

一直报错，但是感觉没错，看不出来了。

#include<bits/stdc++.h>
using namespace std;
//3696构造有向无环图
const int N=2e5+10;
//拉链法存图
int idx=0;
int e[N],h[N],ne[N];//存图
int d[N];//存入度
vector<pair<int,int>>a;
int p[N];//存拓扑序；
void add(int x,int y)
{//先保存当前边的终点//头插法将其插入到h[a]所在的拉链。//h[a]指向新插入的节点//idx++更新e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}int tuopu(int n)
{int cnt=0;queue<int>q;for(int i=1;i<=n;i++){if(!d[i]){q.push(i);p[i]=cnt++;}}while(!q.empty()){auto t=q.front();//拿出队头结点q.pop();for(int i=h[t];i!=-1; i=ne[i])//找所有出边指向点的idx{d[e[i]]--;if(d[e[i]]==0){p[e[i]]=cnt++;q.push(e[i]);}}}return cnt;
}int main()
{int T,n,m,t;cin>>T;while(T--){memset(h,-1,sizeof(h));memset(d,0,sizeof(d));cin>>n>>m;while(m--){int x,y;cin>>t>>x>>y;if(t)add(x,y),d[y]++;a.push_back({x,y});}if(a.size()!=n&&tuopu(n)!=n)cout<<"NO"<<endl;else{cout<<"YES"<<endl;//如何比较两个点的拓扑序for(auto t:a){int q=t.first;int z=t.second;if(p[q]<=p[z])cout<<q<<" "<<z<<endl;else cout<<z<<" "<<q<<endl;}}a.clear();}}

//848拓扑排序

#include<bits/stdc++.h>
using namespace std;
//848拓扑排序
int n,m;
const int N=1e5;
int e[N],ne[N],h[N],idx,d[N],p[N];
void add(int x,int y)
{e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}int tuopu()
{queue<int>q;int cnt=0;for(int i=1;i<=n;i++){if(!d[i]){//cout<<"000000"<<endl;q.push(i);p[cnt++]=i;}}while(!q.empty()){//cout<<"queue"<<endl;int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int u=e[i];d[u]--;if(!d[u])q.push(u),p[cnt++]=u;}}if(cnt==n)return 1;return 0;
}
int main()
{cin>>n>>m;memset(h,-1,sizeof(h));memset(d,0,sizeof(d));while(m--){int x,y;cin>>x>>y;add(x,y);d[y]++;}if(tuopu()==1){for(int i=0;i<n;i++){cout<<p[i]<<" ";}}else{cout<<-1<<endl;}
}