Building adjacency list: where is the number of edges. DFS visits each vertex once and each edge twice (once from each endpoint): . Computing low-link values and checking bridge conditions: per edge.
Total time complexity: . This is best because you need to look at every edge at least once to determine if it is a bridge. Space complexity: for recursion stack and arrays.