EDGEDIR - Editorial(Unofficial)

[pandey_ji1]

Problem Link:

Contest

PREREQUISITES:

Graph theory, Basic graph algorithms

Difficulty: Easy-medium

PROBLEM:

Given an undirected(connected) graph with N vertices and M edges, direct the edges(make a directed graph consisting of the same edges directed in either forward or backward direction) in such a manner that indegree of all the vertices is even or print that it is not possible.

EXPLANATION:

Given N, we know that there are N vertices. So we take N disjoint sets, and while taking the edges as input, we check using union-find algorithm whether inclusion of this particular edge causes the formation of cycle. If yes, we’ll not include this edge in our tree for now. We’ll store every such edge in a different list, say L.

After the above step, we now have one spanning tree of the given graph. Now, perform Depth First Search on any node(since it is a connected graph) and orient the edges in the direction of DFS. This operation gives us a Directed Acyclic Graph(DAG).

Now, insert the extra edges from list L into the graph obtained after the above step in such a manner that it remains a DAG after inclusion of these extra edges. For that, we need to topologically sort the vertices. Thus, if we have an extra edge between u and v, and in topological ordering, u comes before v, then we direct the edge from u to v, otherwise from v to u. In this way, we have now included all the edges while retaining the properties of the DAG.

Now, traverse each node from the adjacency list and store its parents in a set. [vector<set> parents(n)]. Also, store the indegree of every vertex in an array, say indegree[].

Now, begin from the node(s) which has no children. If its indegree is not even, reverse the direction of one incoming edge to this node, without caring about its parent. Once its indegree is even, traverse all of its parents and repeat the same procedure for every node.

In this way, we reach the root node of our DAG which has no parents. Here, if its indegree is not even, we can be sure that the given graph cannot be converted to a directed graph in which every vertex has an even indegree. If the indegree of the root is even, then the graph has been converted to the desired graph. Hence we compare its edges with the given graph’s edges and print the desired output.

This gives us a linear time complexity to reach the desired output!

1. Make a spanning tree.
2. Perform DFS on this tree and orient edges to obtain a DAG.
3. Topologically sort this DAG and insert the extra edges which were not in the spanning tree while
   maintaining the DAG property.
4. Backtrack from the leaves up towards the root making indegree of every vertex even.

**EDIT: ** Nima came up with a point which I would like to bring into everyone’s notice: If number of edges is odd, the solution is impossible. Else, solution is always possible! Thanks Nima! /

Time Complexity:

O(V+E)=O(N+M)

SOLUTION:

Author

[rds_98]

Access Denied on the Solution

[nima101]

Interesting approach.

I did it a bit differently:

1. if num(edges) is odd → impossible (because you have odd indegrees in total)
2. if num(edges) is even → you can always do it

You can prove (2) with induction and use it to also direct the edges.
each step of induction is:

1. find two edges that share a vertex (a-b and b-c) such that removing them doesn’t disconnect the graph (note*)
2. direct them as (a->b and b<-c)
3. remove them from the graph and go to step 1.

note*: connectivity is in terms of edges. we don’t want edges of the graph to be split into two separate components but it is ok to leave vertex “b” disconnected from the graph after removing the two edges.

So, we start with a connected graph with even edges. Each step removes two edges and keeps the graph connected. (also note that removing those edges doesn’t have any impact on the remaining graph because we don’t care about outgoing degrees) So the induction invariant is maintained (connected graph & even edges). The base case is num(edges) = 0, which is when we are done.

Now, the main challenge in implementing this is to remove pairs of edges that share a vertex and don’t disconnect the graph. To do that, I picked a random vertex as seed, did BFS from that vertex and labeled vertices with their BFS level (imagine turning the graph into an onion with layers). Now, for each vertex in the outermost layer, as long as their degree is greater than 1, remove pairs of adjacent edges, prioritizing edges that have the other end in a farther layer. if you end up with a remaining degree of 1, just leave it. later when you process the other end of the edge (from an inner layer, you’ll remove that edge first).

my implementation: CodeChef: Practical coding for everyone

[sudhanshu6324]

@pandey_ji can u explain the intuition behind your approach , I mean why this works!!

[black_truce]

Using Simple DFS:

• Make any directed graph with the given edges.

• If Nodes having odd indegree are odd, exit [Not possible].

Simple Idea:

“Flip all edges between 2 odd indegree vertices so they both would have even indegrees.”

• Start DFS from any node.

DFS

• Mark Visited.

• Invert ^= Indegree of this vertex v.

• For all unvisited u, connected to this vertex v,

  - Edge Between v and u ^= Invert
  
  - Call DFS for vertex u
  
  - Edge Between v and u ^= Invert
  

This DFS is simple enough to code under 10 Lines neatly.

Working:

Initialize Invert as 0. Indegree(var) of a vertex is 0 if it’s indegree is even, else Indegree(var) is 1. XOR with 1 inverts, else it remains the same. So, if indegree of some vertex is 1, Invert will flip. If Invert is 1 it means we need to flip the edges on our way. If Invert is 0 we don’t need to flip.

Example:

There is one graph whose only 4 vertices has odd indegree. Let’s name them 1 to 4. Also, there are two branches from vertex 2, one has vertex 1 and other has vertices 3 and 4. If we start DFS from vertex 1, all edges from 1 to 2 would be flipped and all edges from 3 to 4 would be flipped. Now Let’s try DFS from vertex 2. Edges from vertex 2 to vertex 3 would be flipped. Now when it goes to vertex 4, it won’t be able to find its pair so until it reaches vertex 1, all the edges would be flipped in the path. So we can see that edge from vertex 2 to vertex 3 gets flipped twice, resulting in flipping only from vertex 1 to vertex 2 and vertex 3 to vertex 4.

Solution Link

[vikram987]

@pandey_ji in your code while adding the extra edge after the topological sort you have the below code
if(pehlekaun[pehla]>pehlekaun[dusra])
adj[dusra].push_back(pehla);
else
adj[pehla].push_back(pehla);

Shouldn’t the else condition be
adj[dusra].push_back(pehla);

Anyhow I ran the code with both the conditions and both seem to give correct answer.
Am I missing something or are the test cases week ?

[pandey_ji1]

The solutions haven’t been made public yet by the host! They won’t take much time hopefully.

[rds_98]

can u post using ideone

[pandey_ji1]

Link to my solution on ideone with sample test cases: PvaHdF - Online C++0x Compiler & Debugging Tool - Ideone.com

[l_returns]

Performing a DFS will treat it like a tree isn’t it ?
Then why don’t we do a solution using only DFS :D…
One of my friend did… I think it’s a correct approach…

[shivam_g1470]

i did using simple bfs

[pandey_ji1]

I too tried bfs method @shivam_g1470 , but my code wasn’t working on the sample cases. Maybe I didn’t cover all the cases. However, I wasn’t convinced with that solution, hence I came up with this intuition and it worked well! ;-))

[pandey_ji1]

@l_returns yes we’re treating the given graph like a tree. And yes, I went through the solutions of several people and found out that we can do it using DFS only too. Peace!

[pandey_ji1]

@nima101 your solution is a better and smarter approach! _/_

[pandey_ji1]

@sudhanshu6324 first I’m converting the graph to a DAG so that there won’t be any cycle which would make it tough to update the indegree of a vertex belonging to that cycle. Then, I’m simply updating the indegree of every vertex starting from leaves in bottom-up fashion till the root! That’s it!

[l_returns]

Okay great

[pandey_ji1]

@vikram987 thanks for pointing out the error! That was kind of a severe error! I can’t believe how this solution got accepted with such error. The code actually got accepted at once. Maybe the test cases were weak enough because I’m adding self loop there(by mistake though) and it’s still passing! Thanks anyway for the correction!! <3

[pandey_ji1]

@black_truce I went through your solution. Time complexity is pretty much similar to that of my solution. But my solution is more complex indeed! Good work!!