比赛&训练|Codeforces E. Directing Edges (拓扑排序 / 构造有向图) (Round #656 Div.3) 比赛&训练|图论

传送门
题意：给出一个图的m条边，属性为1表示有向边，属性为0表示无向边。试问是否可确定所以无向边的方向，使图变成一个没有环的有向图？若无可行方案输出"NO"，反正输出"YES"并输出原无向边确定的方向。

文章图片

思路：

若原图就已经成环，那么必然输出NO，否则就一定可以构造出可行解。
考虑原图的拓扑排序，根据两点的进队时间，对于某一无向边，只要使边上两点进队时间也满足拓扑序，就可以使得图依旧无环。
具体看代码，详细思路可参考这篇博客。

【比赛&训练|Codeforces E. Directing Edges (拓扑排序 / 构造有向图) (Round #656 Div.3)】代码实现：

#include #define endl '\n' #define null NULL #define ll long long #define int long long #define pii pair #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 intinf = 0x7fffffff; const double PI = acos(-1.0); const double eps = 1e-6; const llmod = 1e9 + 7; const intN = 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 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; } else cout << v + 1 << " " << u + 1 << endl; } }return 0; }