How to make a graph strongly connected by swapping its edges

Question

How can I calculate the number of steps required to make a directed graph strongly connected by swapping edges? A step is an edge swap.

Note: Every node will have an in-degree of 1 and an out-degree of 1.

Eg-> 1->3, 2->1, 3->2 and 4->4 is not strongly connected. Now, if we swap 4->1 and 2->4 then it becomes strongly connected.

I'm still having trouble understanding your question. Could you elaborate more and post your code here? — user5283155
Is it necessary, that every node will have 1 in-degree and 1 out-degree. because you have explained such eg. — surajs1n
Yes it is given that every node will have 1 in-degree and 1 out-degree. — reaper1

surajs1n surajs1n · Accepted Answer · 2015-09-13T04:34:12

Now, the solution goes like this:

First, calculate total number of disjoint cycles or loops in the graph you have let say the number of disjoint cycle or loops are N.
Print N-1, that would be your answer to this question. (N-1 Why ? Think).