Critical Connections - Time Complexity

Building adjacency list: $O(E)$ where $E$ is the number of edges. DFS visits each vertex once and each edge twice (once from each endpoint): $O(V + E)$. Computing low-link values and checking bridge conditions: $O(1)$ per edge.

Total time complexity: $O(V + E)$. This is best because you need to look at every edge at least once to determine if it is a bridge. Space complexity: $O(V)$ for recursion stack and arrays.