Editorial for CEOI '17 P1 - One-Way Streets
Submitting an official solution before solving the problem yourself is a bannable offence.
The problem is asking whether individual edges in a directed version of the given graph must have a fixed orientation to maintain reachability between the given pairs of nodes.
Cycles. Consider a cycle in the graph. We can direct all the edges to form a directed cycle in one or the other direction. This way, all nodes are reachable from each other within a cycle. Compress the cycle into a single node and repeat the process until there are no more cycles left and we're left with a forest. We could start with any cycle in any direction, therefore the answer for all compressed edges is B
. Because there is a unique path between a pair of nodes (if they are part of the same component), these edges will have a fixed orientation. Just direct the edges along the path from the start to destination. This solves the problem but not efficiently enough.
Bridges. After compressing the cycles, we're left with a tree. The edges in this tree are the bridges of the original graph, which we can find in linear time with Tarjan's algorithm. This solves the second subproblem.
Lowest Common Ancestor. The only source of inefficiency stems from directing the edges in a tree. Going over every edge in every path takes too much time and we might direct the same edge several times. Can we avoid this? One approach is to process the paths in a helpful order. Let's root the tree at some node and process it in
Comments