Costruisci il grafo orientato dei componenti e parti a costruire la catena dalla fine scegliendo sempre il numero massimo che puoi scegliere di componenti che non hanno archi in uscita e rimuovendo gli archi entranti in esso (se lavori contemporaneamente sul grafo e sul suo trasposto fai prima)
Esce una catena diversa da quella da te proposta ma dovrebbe essere sempre di lunghezza minima, anche se non mi sono posto il problema di dimostrarlo...
Esempio
A -> B C A S
B -> S
C ->
D -> S
S -> X
X ->
X&C
A -> B D S
B -> S
D -> S
S ->
S X&C
A -> B D
B ->
D ->
B&D S X&C
A ->
A B&D S X&C
Rispondi quotando