topsort

被拓扑排序给安排了
这道题让我们给边加方向让,最终的图没有环。
其实没有环就意味着他是一个DAG所以他一定有一个拓扑序
这点我是想到了
但是,思维能力不够。我做响了错误的方向。把这道题做的极其困难。
我们可以先并不关心没有方向的边。我们先处理有方向的边。
将有方向的边建一个拓扑序。然后让我方向的边遵照这个拓扑序进行方向的选定就好了!!!!
真的是太妙了。因为我不熟悉拓扑排序所以没有想到。
虽说是套路题,但是我觉得是好题!!

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
typedef pair<int,int> pii;
const int max_n = 2e5+100;
vector<int> G[max_n];
int n,m;
int ts[max_n];
int ru[max_n];
bool topsort(){
    deque<int> que;
    for (int i=1;i<=n;++i)if (ru[i]==0)que.push_back(i);
    int st=0;
    while(!que.empty()){
        int u = que.front();que.pop_front();
        ts[u]=++st;
        for (int v:G[u]){
            --ru[v];
            if (ru[v]==0)que.push_back(v);
        }
    }return st==n;
}

int main(){
    int t;cin>>t;
    while(t--){
        vector<int> tps;
        vector<pii> es;
        cin>>n>>m;
        for (int i=0;i<=n+10;++i)G[i].clear(),ru[i]=0;
        for (int i=1,ty,u,v;i<=m;++i){
            cin>>ty>>u>>v;
            if (ty==1)G[u].push_back(v),ru[v]++;
            else es.push_back(pii(u,v));
        }
        if (!topsort()){
            cout<<"NO\n";
            continue;
        }
        cout<<"YES\n";
        for (int i=1;i<=n;++i)for (int v:G[i])cout<<i<<" "<<v<<endl;
        for (pii p : es){
            if (ts[p.first]>ts[p.second])swap(p.first,p.second);
            cout<<p.first<<" "<<p.second<<endl;
        }
    }
}