Jag har insett att lösningen till uppgift 2.1 på förra tentan är väl kortfattad. Jag föreslår därför följande omarbetade version:

Använd DFS och låt algoritmen numrera noderna i ordningen de besöks. Vi definierar också en array backcycle[u]. Värdet på denna array är tänkt att vara det lägsta värde som man kan nå från u med en cykel som går "framåt" till en redan besökt nod. Vi initierar backcycle[u] till "oändligt" och gör sedan följande: När vi gör DFS-sökningen och från u når en redan besökt nod v sätter vi backcycle[u] = Min(backcycle[u],v). När vi sedan back-trackar (går bakåt i sökträdet) längs en kant, t.ex. (a,b) där a < b sätter vi backcycle[a] = Min(backcycle[a],backcycle[b]). När vi sedan kört algoritmen kollar vi alla kanter. Antag att vi har en kant (a,b) med a < b. Då är kanten en bro om och endast om backcycle[b] > a. DFS-sökningen går i tid O(|V|+|E|)). (De moifikationer vi gjort i sökningen ändrar inte detta. Eftersom grafen är sammanhängande är O(|V|+|E|)) = O(|E|). Den sista genomgången av kanter tar också tid O(|E|) som också blir totala tidskomplexiteten.