给定一张图，图中给出一些有向边，一些无向边。
要求给所有无向边赋予方向后能够使整张图无环。
已知给定的图中无自环，无重边
解题思路：
若给定的有向边已经成环，那么必然输出NO，否则都可以构造出解。
考虑原图的拓扑排序，根据两点的进队时间，对于某一无向边，只要使边上两点进队时间也满足拓扑序，就可以使得图依旧无环。
#pragma warning(disable:4996) #include<iostream> #include<algorithm> #include<bitset> #include<tuple> #include<unordered_map> #include<fstream> #include<iomanip> #include<string> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<list> #include<queue> #include<stack> #include<sstream> #include<cstdio> #include<ctime> #include<cstdlib> #define INF 0x3f3f3f3f #define inf 0x7FFFFFFF #define MOD 998244353 #define moD 1000000003 #define pii pair<ll,int> #define eps 1e-8 #define equals(a,b) (fabs(a-b)<eps) #define bug puts("bug") #define re register #define fi first #define se second #define pb push_back const int maxn = 1e6 + 5; const double Inf = 10000.0; const double PI = acos(-1.0); typedef long long ll; typedef unsigned long long ull; using namespace std; vector<int> vec[maxn]; int InDeg[maxn]; queue<int> q; int num; int n; int t[maxn]; bool topsort() { while (!q.empty()) q.pop(); num = 0; for (int i = 1; i <= n; i++) if (!InDeg[i]) q.push(i); int tt = 0; while (!q.empty()) { int now = q.front(); q.pop(); num++; t[now] = tt++; for (int i = 0; i < vec[now].size(); i++) { if (--InDeg[vec[now][i]] == 0) q.push(vec[now][i]); //入度为零，进入队列 } } return n == num; } void solve() { int tmp, x, y; memset(InDeg, 0, sizeof InDeg); memset(vec, 0, sizeof vec); memset(t, 0, sizeof t); int m; scanf("%d%d", &n, &m); vector<pii> ans; vector<pii> res; for (int i = 0; i < m; i++) { scanf("%d%d%d", &tmp, &x, &y); if (tmp == 1) vec[x].push_back(y), InDeg[y]++, res.emplace_back(x, y); else ans.emplace_back(x, y); } if (!topsort()) { puts("NO"); return; } for (int i = 0; i < ans.size(); i++) { if (t[ans[i].first] > t[ans[i].se]) res.emplace_back(ans[i].se, ans[i].fi); else if (t[ans[i].first] <= t[ans[i].se])res.emplace_back(ans[i].fi, ans[i].se); } puts("YES"); for (int i = 0; i < res.size(); i++) printf("%d %d\n", res[i].fi, res[i].se); } int main() { int T; scanf("%d", &T); while (T--) solve(); }