题目链接
题目大意
这道题就是给你一堆边,有些边是确定方向的,有些边是不确定方向的,问你将这些不确定方向的边怎么放满足这个图是一个有向无环图
题解
这道题问是不是有向无环图,那么就是问是不是拓扑图,所以要进行拓扑排序,如果已有的边已经不是拓扑图,那么怎么加边也不是拓扑图,所以先判断给的确定的边是不是拓扑图,如果是拓扑图,那么肯定会算出来一个拓扑序,然后把那些不确定的边按照拓扑序排列即可。这个鬼题别忘了将所有的全局变量都初始化,要不然出现一堆什么鬼,pos标记的时候刚开始用的是vector开了n的大小,我就不知道为啥会报错,换成map就过了。
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
int d[N];
vector<int> ans;
vector<PII> v;
vector<int> a[N];
bool topsort()
{
queue<int> q;
for (int i = 1; i <= n; i++) {
if (!d[i])
q.push(i);
}
while (q.size()) {
auto t = q.front();
ans.push_back(t);
q.pop();
for (auto x : a[t]) {
if (--d[x] == 0) {
q.push(x);
}
}
}
return ans.size() == n;
}
void solve()
{
memset(d, 0, sizeof d);
ans.clear();
v.clear();
cin >> n >> m;
for (int i = 1; i <= n; i++) {
a[i].clear();
}
while (m--) {
int op, x, y;
cin >> op >> x >> y;
if (op) {
a[x].push_back(y);
d[y]++;
} else {
v.push_back({ x, y });
}
}
if (!topsort())
cout << "NO\n";
else {
cout << "YES\n";
unordered_map<int, int> pos;
for (int i = 0; i < ans.size(); i++) {
pos[ans[i]] = i;
}
for (int i = 1; i <= n; i++) {
for (auto x : a[i]) {
cout << i << " " << x << endl;
}
}
for (auto [x, y] : v) {
if (pos[x] > pos[y])
cout << y << " " << x << endl;
else
cout << x << " " << y << endl;
}
}
}
int main()
{
IOS;
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}