CF1385E Directing Edges 题解

题目链接：CF1385E Directing Edges

题意：

给定一张 \(n\) 个节点 \(m\) 条边的混合图，要求对无向边定向，使得原图不存在环。

输入格式：

多组数据，每组先给出 \(n,m\) ，然后 \(m\) 行形如 \(\mathtt{op\ x\ y}\) 。

若 \(\mathtt{op = 0}\) ，则该图存在无向边 \((u,v)\) 。若 \(\mathtt{op=1}\) ，则该图存在有向边 \(u\to v\) 。

输出格式：

如果可以做到，请输出 YES ，并输出这张图（次序随意）；否则输出 NO 。

数据范围：

\(\sum n \le 2 \times 10^5,~\sum m \le 2 \times 10^5\) 。

考虑先无视无向边，然后对原图做一遍拓扑排序，如果已经有环了肯定无解。

否则对于所有无向边，我们直接让拓扑序小的指向拓扑序大的点。

这样原图就是一个 DAG （有向无环图）了。

时间复杂度 \(\mathcal{O}(Qn)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define Fi first
#define Se second
#define N ((int)(2e5+15))

int n,m,pos=1,head[N],in[N],tp[N]; pii e0[N];
struct Edge { int u,v,next; } e[N];
queue<int> q;
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; ++in[v]; }
void clear()
{
    for(int i=1; i<=n; i++) { head[i] = in[i] = 0; tp[i] = INF; }
    pos = 1; while(!q.empty()) q.pop();
}
bool topo_sort()
{
    for(int i=1; i<=n; i++) if(!in[i]) q.push(i);
    static int tim = 0;
    for(tim = 0; !q.empty(); )
    {
        int u = q.front(); q.pop();
        tp[u] = ++tim;
        for(int i=head[u]; i; i=e[i].next)
        { if(!(--in[e[i].v])) q.push(e[i].v); }
    }
    if(tim != n) return 0;
    return 1;
}
void work()
{
    cin >> n >> m; int o = 0; clear();
    for(int i=1,op,u,v; i<=m; i++)
    {
        cin >> op >> u >> v;
        op ? addEdge(u,v) : (void)(e0[++o] = pii(u,v), 0);
    }
    if(topo_sort())
    {
        cout << "YES\n";
        for(int i=1; i<=n; i++)
            for(int j=head[i]; j; j=e[j].next)
            { cout << i << ' ' << e[j].v << '\n'; }
        for(int i=1; i<=o; i++)
        {
            if(tp[e0[i].Fi] > tp[e0[i].Se]) swap(e0[i].Fi, e0[i].Se);
            cout << e0[i].Fi << ' ' << e0[i].Se << '\n';
        }
    }else return cout << "NO\n",void(0);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; cin >> _Q; while(_Q--) work();
    return 0;
}