Requesting an editorial for Directing edges(EDGEDIR) from December'18 long challege

editorial
, , ,
1

Here is the question link - https://www.codechef.com/DEC18B/problems/EDGEDIR

2

you can have a look at these answers edgedir.

3

Okay so here’s my approach
Let the input graph be a directed graph with edge u,v meaning a edge from u to v.
Now you have two type of vertices

Even indegree

Odd indegree

Now for any odd indeg. Vertex u if any edge u,v or v,u is reversed then the vertex becomes even indeg. Vertex and the vertex u changes it’s type.
The goal is to reverse edges so as to make all the vertices even indegree. Whenever you reverse any given edge two vertices will change their types, so we need number of type 2 vertices to be even(imagine a graph with only 1 odd indegree vertex. Not possible to satisfy.)

Now let’s say number of type 2 vertices are even. select any two of these vertices v1 and v2 and reverse all the edges in the path from v1 to v2. Now v1 and v2 become type 1 without changing the type of any intermediary vertex. You can go on selecting two type2 vertices at a time and reversing all edges on the path between them converting them to type1, however this will TLE.

You can achieve the same thing using only a single DFS. start the DFS if you encounter a type2 vertex keep Reversing all edges till you encounter another type2 vertex and continue The same for rest of the DFS.

Let me know if it’s not clear.