Given a graph G and a subset of vertices A, write an efficient algorithm that prints if they exist, two sets B, C subsets of V such that:
- B intersected C is a subset of A
- Each vertex of B has a path that reaches at least one vertex of A
- Each vertex of C is reachable from at least one vertex of A
my solution(I'm not sure of it) The idea is to construct B by verifying which are the vertices that reach at least one vertex in A through a DFS_Visit on the transposed graph. I construct in a similar way, but on the non-transposed graph, the set C. Finally, I paint the vertices of A with a color that is neither white nor gray nor black, for example, red. If there are vertices that are in both B and C but not A, I return false. If the sets do not exist, the absence of a solution must be reported some pseudocode
Algo(G,A)
B = C = empty
Init(G,A,c1,c2)
Gt = traspose(G)
for each a in A do
if c1[a] = c2[a] = B then
DFS_Visit(Gt,a,c1)
DFS_Visit(G,a,c2)
for each v in V do
if c1[v] = N then
B = B U {v}
if c2[v] = N then
C = C U {v}
for each v in V do
if c1[v] = c2[v] = N and c3[v] != Red then
print "A and B not exist"
return false
Stampa(B,C)
return true
Init(G,A)
for each v in V do
c1[v] = c2[v] = B
for each a in A do
c1[a] = c2[a] = Red