Valid Arrangement of Pairs

Approach: 

In this problem we can consider every pairs[i] as the directed edge from the node pairs[i][0] to the node pairs[i][1]. As all the pairs[i] are distinct from each other and you have to find a valid arrangement of pairs, this means that every edge should be used exactly once. 

The given problem can be boiled down to the following problem:

You are given a directed graph and you have to find an Euler path in this graph. An Euler path is a path that uses every edge of a graph exactly once. Also, it is given that the answer always exists means that the Euler path always exists in the given graph.
 

The first thing we have to do is to create an adjacency list of every node, here we don’t know about the range of the nodes so we will use unordered_map to store the adjacency list of every node, after that, we have created the adjacency list of every node, we will maintain the “in” and  “out” degree of every node, “in” degree of a node is the number of edges coming towards the node and “out” degree of a node is the number of edges going from the node.

 

For finding the Euler path we have to first find the starting node from which we will start the dfs traversal. A valid start node for finding the Euler path is the node which has outDegree- inDegree is equal to 1, and the count of this node will be at most one. If a graph has no such node then we can start from any node in the graph. In the dfs(node, adj, out, path) where “node” is the current node, we are at,  “adj” is the adjacency list of all the nodes, adjacency list stores all the nodes which are directly connected to the ith node, “out” is the vector which stores the out-degree of every node, “path” is the vector which stores the Euler path.

The idea is to start the dfs from the “start” node and just start traversing the edges which are not visited yet after a point we will be at a node “x” which has no out-edge left so, we will push that node into “path” vector and then backtrack to a node which has an out-edge.

For checking whether a node has an out-edge or not we will use “out” vector after we reach any node let’s say “x” we will check whether out[x] is equal to zero or not, if it is zero then we will push the node into “path” vector otherwise we will update out[x] = out[x] - 1 and then call the dfs function from the node adj[x][out[x]], here you can see out[x] acts as an index in the adjacency list of the node “x”, every time it will decrease by 1 thus, we can say that every time we will have a unique edge.
 

Here is the algorithm:

• dfs function:
  • If outDegree of node is equal to 0
    • Push node into “path” vector.
    • Return
  • While (out[node] != 0)
    • Update out[node] as out[node] - 1.
    • dfs(adj[node][out[node]], adj, out, path)
  • Push the node into the “path” vector.

• given function:
  • Declare an unordered map< int, vector < int > > “adj” for storing the adjacency list of all the nodes.
  • Declare an unordered map<int, int> “int”, “out” for outDegree and inDegree of every node in the graph.
  • Create an adjacency list and store the “outDegree” and “inDegree”. This can be done by running a loop where ‘i’ ranges from 0 to ‘pairs.size’-1 and for each ‘i’ push pairs[i][1] in list adj[pairs[i][0] and increase the inDegree of node pairs[i][1] by 1 also increase the outDegree of node pairs[i][0] by 1.
  • Declare a variable “start”, which stores the start node from where “dfs” will start initialize by -1.
  • Iterate over the nodes in the graph(say iterator ‘i’)
    • if( out[node]-in[node] is equal to 1)
    • Set start = node.
  • If flag == -1, means that there is no node such that out[node]-in[node] is equal to 1, then just start from any node of the graph, so just take the node which has the lowest number.
  • Declare a vector “path” for storing the Euler path.
  • dfs(start, adj, out, path)
  • Declare a 2-d vector “ans” for storing the edges in the path, which we have to return.
  • Reverse the “path” vector as we have the path in the reverse order.
  • Iterating over ”path” vector from 0 to path.size -1  (say iterator ‘i’)
    • Insert the edge { path[i], path[i+1] } into the “ans” vector.
  • Return ans.

O( N ), where ‘N’ is the number of pairs given.

 We are touching every edge exactly once and there are ‘N’ number of edges and we are using unordered maps which have lookups in O(1) time and creating an adjacency list will also take O( N ) time, Thus overall time complexity will be O(N). 

O( N ), where ‘N’ is the number of pairs given.

Extra space used by adjacency list “ADJ” is of size O( N ), and recursion stack, “path”, “ans”, “in”, “out” use O(N) space, Thus overall space complexity will be O( N ).