Hi codeforces!↵
I’m stuck on the constructive part of a graph problem.↵
↵
Problem: Given a mixed graph (N <= 100000, M <= 200000) with some fixed (directed) edges and some free (undirected) edges. I already used binary search and Tarjan's algorithm to find a state where a solution is guaranteed to exist (i.e., treating free edges as bidirectional yields exactly 1 SCC).How do I constructively assign a single direction to each free edge so the final directed graph remains a single SCC in O(N+M)?
I’m stuck on the constructive part of a graph problem.↵
↵
Problem: Given a mixed graph (N <= 100000, M <= 200000) with some fixed (directed) edges and some free (undirected) edges. I already used binary search and Tarjan's algorithm to find a state where a solution is guaranteed to exist (i.e., treating free edges as bidirectional yields exactly 1 SCC).How do I constructively assign a single direction to each free edge so the final directed graph remains a single SCC in O(N+M)?
