Блог

Учитывая граф G и подмножество вершин A, напишите эффективный алгоритм, который выводит, если они существуют, два набора B, C подмножеств V, таких что:

1. B пересеченный C является подмножеством A
2. Каждая вершина B имеет путь, который достигает по крайней мере одной вершины A
3. Каждая вершина C достижима по крайней мере из одной вершины A

мое решение(я в этом не уверен) Идея состоит в том, чтобы построить B, проверив, какие вершины достигают хотя бы одной вершины в A через DFS_Visit на транспонированном графике. Я строю аналогичным образом, но на неперемещенном графике множество C. Наконец, я окрашиваю вершины A цветом, который не является ни белым, ни серым, ни черным, например, красным. Если есть вершины, которые находятся как в B, так и в C, но не в A, я возвращаю false. Если наборов не существует, об отсутствии решения необходимо сообщить каким-либо псевдокодом

 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