×

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

 0 Here is the question link - https://www.codechef.com/DEC18B/problems/EDGEDIR asked 31 Dec '18, 18:40 21●3 accept rate: 0%

 0 you can have a look at these answers edgedir. answered 31 Dec '18, 19:34 237●8 accept rate: 10%
 0 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. answered 31 Dec '18, 19:53 3●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,710
×102
×1
×1

question asked: 31 Dec '18, 18:40

question was seen: 170 times

last updated: 31 Dec '18, 19:53