Graph theory, Basic graph algorithms
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.
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!
- Make a spanning tree.
- Perform DFS on this tree and orient edges to obtain a DAG.
- Topologically sort this DAG and insert the extra edges which were not in the spanning tree while
maintaining the DAG property.
- Backtrack from the leaves up towards the root making indegree of every vertex even.