AcWing
3696. 构造有向无环图
拓扑排序。当不考虑无向边时，所有的有向边不构成环路，此时便可以按照一个拓扑序为无向边分配方向。所以可以构造有向无环图等价于所有有向边和顶点构成的图是有向无环图，即，所有有向边和顶点构成的图存在一个拓扑序。使用邻接表存储图。pos数组用来确定元素在拓扑序数组q中的位置。
#include <bits/stdc++.h>
using namespace std;
int t, n, m;
const int N = 200010;
vector<vector<int> > adl;
int ind[N], q[N], pos[N];
struct ue{
int a, b;
}ued[N];
bool topsort(){
int hh = 1, tt = 0;
for(int i = 1; i <= n; i++) if(!ind[i]) q[++tt] = i;
while(hh <= tt){
for(auto i : adl[q[hh]]){
if(!(--ind[i])) q[++tt] = i;
}
hh++;
}
return tt == n;
}
int main(){
cin >> t;
while(t--){
cin >> n >> m;
adl.resize(0); adl.resize(n + 1);
fill(ind + 1, ind + 1 + n, 0);
int cnt = 0; // 无向边的数量
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> c >> a >> b;
if(c){
adl[a].push_back(b);
ind[b]++;
}
else{
++cnt;
ued[cnt].a = a;
ued[cnt].b = b;
}
}
if(!topsort()) cout << "NO" << endl;
else{
cout << "YES" << endl;
for(int i = 1; i <= n; i++) for(auto j : adl[i]) cout << i << ' ' << j << endl;
for(int i = 1; i <= n; i++) pos[q[i]] = i;
while(cnt){
int a = ued[cnt].a, b = ued[cnt].b;
if(pos[a] > pos[b]) swap(a, b);
cout << a << ' ' << b << endl;
cnt--;
}
}
}
return 0;
}