传送门
题意： 给出一个图的m条边，属性为1表示有向边，属性为0表示无向边。试问是否可确定所以无向边的方向，使图变成一个没有环的有向图？若无可行方案输出"NO"，反正输出"YES"并输出原无向边确定的方向。
样例输入：
4
3 1
0 1 3
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5
4 5
1 1 2
0 4 3
1 3 1
0 2 3
1 2 4
4 5
1 4 1
1 1 3
0 1 2
1 2 4
1 3 2
样例输出：
YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO
第二组样例示意图：
第三组样例示意图：
思路：
- 若原图就已经成环，那么必然输出NO，否则就一定可以构造出可行解。
- 考虑原图的拓扑排序，根据两点的进队时间，对于某一无向边，只要使边上两点进队时间也满足拓扑序，就可以使得图依旧无环。
- 具体看代码，详细思路可参考这篇博客。
代码实现：
#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
using namespace std;
const int inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll mod = 1e9 + 7;
const int N = 2e5 + 5;int T, n, m, tpcnt, ok;
int h[N], e[N], ne[N], idx;
//q统计经过处理后入度为0的点， d记载每个点的入度
int d[N], tp[N]; //tp用来记录该点是拓扑排序中被标记为第几struct node{
int x, u, v;
}mp[N];//领接表存图
void add(int u, int v)
{
e[idx] = v;ne[idx] = h[u];h[u] = idx ++;d[v] ++;
}
//初始化数组
void Inint(){
idx = tpcnt = 0;me(d); mem(h, -1);
}bool topsort()
{
queue<int> q;for(int i = 0; i < n; i ++)if(!d[i]) q.push(i);while(q.size()){
int t = q.front(); q.pop();tp[t] = tpcnt ++;for(int i = h[t]; ~i; i = ne[i]){
//与该点连接的所有点都要减去一个入度int j = e[i];d[j] --; //如果入度为零了，放入队列if(!d[j]) q.push(j);}}return tpcnt == n; //如果遍历了所有的点，说明没有环路。
}signed main()
{
IOS;cin >> T;while(T --){
cin >> n >> m;Inint();for(int i = 0; i < m; i ++){
int x, u, v; cin >> x >> u >> v;mp[i] = {
x, -- u, -- v};if(x) add(u, v);}ok = topsort();if(!ok){
cout << "NO" << endl;continue;}cout << "YES" << endl;for(int i = 0; i < m; i ++){
int x = mp[i].x , u = mp[i].u, v = mp[i].v;if(x || tp[u] < tp[v]){
cout << u + 1 << " " << v + 1 << endl;}elsecout << v + 1 << " " << u + 1 << endl;}}return 0;
}