You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 31 Dec '18, 18:40

devansh1497's gravatar image

4★devansh1497
213
accept rate: 0%


you can have a look at these answers edgedir.

link

answered 31 Dec '18, 19:34

vipin_bhardwaj's gravatar image

5★vipin_bhardwaj
2378
accept rate: 10%

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.

link

answered 31 Dec '18, 19:53

kartik8800's gravatar image

5★kartik8800
32
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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