undirected graph is given which has M edges and N vertices we have to convert every edge from u-v to u->v or v->u such that indegree of every vertex is even.Which method or algorithm is suited for least time complexity.
0
votes
How large your graph is? What are the limits of M and N? I think this question is better suited at cs.stackexchange.com Also, it would help a lot if you could explain your problem and your attempts a little more. As of now it looks like you just want someone to do your homework for you :) Please edit this question and put in more details.
– inquisitive
M and N are from 1 to 100,000. I made a adjacency list which keeps track of all edges coming to the particular vertex which means if 1->2,3->2,4->2 then adjacency list of 2 will be {1,3,4} so if size of adjacency list is even for every vertex then I will know the direction of every edge I made it even with while loop that while loop will only terminate when every vertex will have even degree. and every time while loop will change direction in those adjacency list whose size is odd
– Faizan Syed
3 Answers
2
votes
Here's a different approach - I don't reckon you want to do Gaussian elimination with n=100,000 so I did a web search for related problems.
If the graph has more than one connected component, you can consider them separately, so let's assume it only has one.
Build a spanning tree on your component and mark one of the vertices the root of that tree. Fix the directions of the edges not on the spanning tree however you like. Take each vertex one at a time starting from the leaves, dealing with all of the children of a vertex before you deal with that vertex. For each vertex, chose the direction of the tree edge up to its parent so that its own indegree is even, and ignoring the consequences for its parent. Each vertex except the root has an edge joining it with its parent, so for every vertex except the root you can make sure that its indegree is even.
When you come to the root you don't have any edges left with a direction you can change, so you can't change its indegree, which is clearly either even or odd. If it is even all is well - every vertex has even indegree. If it is odd, you have one vertex with odd indegree and all the others with even indegree, so the sum of all of the indegrees is odd. But the sum of all of the indegrees is just the number of edges in the graph, which you can't change. If the number of edges in the graph is odd there will always be at least one vertex with odd indegree, and the problem was impossible anyway.
2
votes
You can do something like this --> Only change you will have to make is, make MST before doing topological
https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/
1
votes
Give each edge an arbitrary direction, and create a variable (currently unknown) which says whether that edge's direction needs to be changed.
For each vertex an edge is incoming according to either x or 1^x, where x is the unknown for that edge and 1^x is 1 XOR x = NOT x, depending on whether the original direction assigned to that edge was towards that vertex or not.
For each vertex, the number of incoming edges is even if the result of xoring together the results of these equations is 0 - which is the same thing as saying the result of adding them together mod 2 is 0.
So you have a system of linear equations mod 2, which is the same thing as binary linear equations, and you can use Gaussian elimination to see if there is a solution.
(There might be a more graph-theoretical way of doing this, but I think this is a solution).
