Find all disconnected directed (cyclic) subgraphs and transform them into stars
Probably you want to compute weakly connected components, a subgraph having a path between every two vertices in the underlying undirected graph. Computing the weakly connected components is easy: first transform the directed graph into undirected by removing "directions" of each edge and run DFS/BFS on that graph (by looping on vertices!). Alternatively, if you're interested in the strongly connected components then you should run one of the algorithms computing SCCs. This gives you components $C_1, \dots, C_n$. 

Then you can do whatever you want to do on these components.