I try to explain my problem better.
in input I have the number of nodes N and the number of edges P.
N represent the cities while P the water pipes.
So for example in input I have 4 and 2 {0,1,2,3,4} would be my graph and the 2 represents me the already existing water pipes
since in the following lines of the file I will have the already existing connections so since in this case I have the 2 for example in the file I'll have 3-1 and 2-1. so at the beginning I will have a graph with 5 vertices and an edge that goes from node 3 to node 1 and another arc that goes from 2 to 1.
now I have to determine how many and which connections to make to bring water to all the cities. so for example in this case a solution could be 0-4,0-3,0-2.
NOTE 0 represents the dam basin.
I was thinking that this problem seems to me very similar to MST but the graph I have is oriented and not weighted so I cannot apply the Prim or Kruskal algorithm. So since it doesn't make sense to apply MST maybe I could do this via a DFS or a BFS but I don't quite understand how.
I believe that if I do a dfs from the source then from node 0 and I see all the nodes that I have not been able to reach and I connect these nodes to the source I have the solution but I have not understood how to do it.
or would it be better to try to make l mst work on this type of graph then cloning it and adding weights = 1 to the arcs?
" I know I can't apply it for the type of graph I have"
How do you know this?
Unweighted. Make your graph weighted by applying a weight of 1 to every edge.
Undirected. Make your graph directed by replacing every edge with two directed edges, one going each way.