Directing Edges -- CF 1385E

Difficulty: 1700 * Techniques: topological sort, DAG orientation, graph construction Problem Link

Quick Revisit
PROBLEM: Orient undirected edges so the mixed graph becomes a DAG
KEY INSIGHT: If directed edges alone form a DAG, orient undirected edges forward in topo order. Otherwise impossible.
TECHNIQUES: topological sort (Kahn's), DAG, constructive
TRANSFER: Mixed directed/undirected "make a DAG?" -- check directed-only for cycles, orient the rest along topo order.

First Read

A graph with some directed and some undirected edges. Orient all undirected edges so the result is a DAG (no directed cycles). If impossible, say so.

My immediate thought: "This smells like topological sort." But how do undirected edges interact with topo sort?

The SCC Dead End

My first idea: compute SCCs of the directed edges, check if adding undirected edges could force a cycle. Maybe orient undirected edges to avoid merging SCCs?

This got complicated. SCC gives you the condensation, but reasoning about how undirected edges interact with it is messy. I was overthinking it.

Stepping Back: When Is It Impossible?

The answer is NO if and only if the directed edges alone already form a cycle. Because if the directed edges are a DAG, we can always orient the undirected edges to keep it a DAG. And if the directed edges have a cycle, no orientation of undirected edges can fix that.

Wait, is that right? Let's verify. If directed edges form a DAG, we have a topological order $π$ . For any undirected edge $(u, v)$ , orient it from the node earlier in $π$ to the node later in $π$ . This can never create a cycle because we're only adding edges that go forward in the topo order.

That's it. That's the whole solution. I spent 15 minutes on SCCs when the answer was "just topo sort the directed part."

The transferable pattern: a topological order is a certificate

The proof above is actually a single reusable idea worth naming explicitly. A topological order $π$ of a directed acyclic graph is a certificate of acyclicity: every directed edge points forward in $π$ . If we then add new edges that also point forward in $π$ , every edge in the new graph still points forward, so $π$ remains a topological order of the augmented graph -- which means the augmented graph is still a DAG. The certificate survives the augmentation.

That single observation is the whole problem. Whenever you face "I have a partial DAG, can I extend it without breaking acyclicity?", reach for the same pattern: produce a topo order of the fixed part, then orient or add the flexible part forward in that order.

The Algorithm

Build a graph with only the directed edges.
Attempt topological sort (Kahn's algorithm / BFS).
If the topo sort fails (cycle detected), output NO.
If it succeeds, assign each node its topo-order index.
For each undirected edge $(u, v)$ : orient it so the node with smaller topo index points to the one with larger topo index.
Output all edges (directed ones as-is, undirected ones with their new orientation).

Implementation Notes

The graph may be disconnected -- Kahn's algorithm handles this naturally (some nodes may start with in-degree 0 even if disconnected from others). If the topo sort processes fewer than $n$ nodes, there's a cycle.
Careful with the output format: we need to print edges in order, preserving which are originally directed.
Store edges in input order. For undirected edges, decide orientation at output time.

The Code

cpp

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int,int,int>> edges(m);
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);

    for (auto& [t, u, v] : edges) {
        cin >> t >> u >> v;
        if (t == 1) {
            adj[u].push_back(v);
            indeg[v]++;
        }
    }

    // Kahn's topo sort on directed edges only
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);

    vector<int> order(n + 1);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order[u] = cnt++;
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }

    if (cnt < n) { cout << "NO\n"; return; }

    cout << "YES\n";
    for (auto [t, u, v] : edges) {
        if (t == 1) {
            cout << u << " " << v << "\n";
        } else {
            if (order[u] < order[v]) cout << u << " " << v << "\n";
            else cout << v << " " << u << "\n";
        }
    }
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

Transfer Lesson

Mixed directed/undirected "can we make a DAG?" -- check if directed edges alone form a DAG. If yes, orient undirected edges along the topological order. Simpler than it seems.
Topological order as a universal orienter -- any edge oriented "forward" in a topo order can never create a cycle. This is a powerful tool for orientation problems.
When your first idea (SCC) feels too complex -- step back and ask "what's the simplest condition for YES/NO?" Often the answer is embarrassingly direct.

Directing Edges -- CF 1385E ​

First Read ​

The SCC Dead End ​

Stepping Back: When Is It Impossible? ​

The transferable pattern: a topological order is a certificate ​

The Algorithm ​

Implementation Notes ​

The Code ​

Transfer Lesson ​