[ALGORITMO] Componenti biconnesse e nodi di taglio

[phate_]

Buonasera a tutti!

Devo scrivere un programma che preso in input un file che descrive un grafo (non vi annoio con i dettagli, non è li il problema) restituisca il numero di componenti connesse, biconesse e nodi di taglio a video. Per il numero di componenti connesse nessun problema, si utilizza una versione modificata della DFS. Per i nodi di taglio ugualmente dovrebbe bastare eliminare "a turno" un nodo dal grafo e vedere se cambia il numero di componenti connesse (ammesso che non esista nulla di più efficiente...). Ma per il numero di componenti biconesse (che sarebbero le 2-connesse) come fare?

Poi mi chiedevo se c'è un modo di fare tutto questo con un'unica visita (o comunque in modo più efficiente dal punto di vista della complessità)... Ma questo è il meno XD

[alka]

Linguaggio?

Hai letto il Regolamento?

[phate_]

Si, l'ho letto... Non mi pare di averlo violato (se sbaglio dimmi pure dove). Non ho chiesto un linguaggio specifico appunto perchè mi basta lo pseudocodice o anche solo l'idea risolutiva (e poi nei grafi i problemi di implementazione non sono indifferenti... quindi mi pareva più semplice una richiesta di questo tipo).

Io comunque per ora avevo in mente di scrivere un programma di questo tipo:

Calcolo il numero di componenti connesse del grafo;
Per ogni nodo:

• rimuovo il nodo ed i suoi archi dal grafo;
  ricalcolo il numero di componenti connesse;
  se aumenta, quello era un nodo di taglio;
  reinserisco il nodo;

Solo che mi rimane il problema delle componenti biconnesse che non so proprio come affrontare

[alka]

Originariamente inviato da phate_
Non ho chiesto un linguaggio specifico appunto perchè mi basta lo pseudocodice

Va comunque specificato, altrimenti non è possibile saperlo.
Correggo il titolo.