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

×

EDGEDIR - Editorial

PROBLEM LINK:

Div 1 Div 2 Practice

Author: Full name Tester: Full name Editorialist: Oleksandr Kulkov

DIFFICULTY:

MEDIUM

PREREQUISITES:

Spanning trees, dp on trees

PROBLEM:

You have undirected connected graph with $N$ vertices and $M$ edges. You have to direct edges of the graph in such a way that indegree of each vertex is even. ($1 \leq N, M \leq 10^5$)

QUICK EXPLANATION:

Direct edges in arbitrary way. Now you may choose any path in initial graph and inverse all edges on this path. In such way you will change indegrees only of first and last vertices on the path, thus you may group vertices of odd indegrees in pairs and get rid of them.

EXPLANATION:

Assume that edges of the graph are already directed in some way. What will happen if we inverse edge $u \to v$? Parities of indegrees of both $u$ and $v$ will inverse as well, because $u$ will have one more edge among edges directed to it and $v$ will lose one such edge. This is the simplest case of edge inversion and any other one may be simply reduced to it. Note that parity of vertices having odd indegree will never change when inverting one edge, this gives us simple criteria of when solution exists: Solution exists $\iff$ amount of vertices having odd indegree is even.

Now what to do if solution exists? Consider path $v_1 \to v_2 \to \dots \to v_{k-1} \to v_k$. What will happen if we invert all edges in such path? Answer is that parity of indegrees of $v_1$ and $v_k$ will be inversed and parity of $v_2, \dots, v_{k-1}$ won't change. Thus if amount of vertices having odd indegrees is even, you may make them in pairs in arbitrary way and one by one inverse all edges in pathes between vertices in each pair. And now you have pretty vast space on implementation of this.

First of all you should note that you may always choose path from some spanning tree (e.g. dfs tree). This would reduce problem to "invert edges on the path in tree several times, output final state of each edge". And now you may either honestly group vertices in pairs and do such queries with some data structure or you may see that inverting path between $u$ and $v$ is the same as firstly inverting path from $u$ to $w$ and then from $v$ to $w$ where $w$ is arbitrary vertex in the tree. This provides you with easiest solution if you simply choose $w$ to be the root of the tree. Then no matter how you split vertices in pairs, you will simply need to invert all edges in set of pathes $w \to v_1, w \to v_2, \dots, w \to v_k$ where $v_1, \dots, v_k$ is the set of vertices having odd indegree and $w$ is the root of the tree. You may process such queries in offline with simple dp counting number of vertices with odd indegree in each's vertex subtree.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 23 Dec '18, 10:58

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 06 Jan, 22:28

admin's gravatar image

0★admin ♦♦
19.7k350498541

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:

×2,559
×146

question asked: 23 Dec '18, 10:58

question was seen: 440 times

last updated: 06 Jan, 22:28