# Problem:
In an undirected connected graph, i must devise an efficient algorithm to indentify all bridge edge cases in the graph.

# Sample Solution:

algorithm descripition

def find_bridges(graph):
    # graph: adjacency list, nodes labeled 0 n-1
    n = len(graph)
    time = 0
    visited = [False]*n
    disc = [0]*n          # Shouldd handle discovery time
    low = [0]*n           # should handle lowest reachable ancestor.. 
    parent = [-1]*n
    bridges = []

    def dfs(u):
        nonlocal time
        visited[u] = True
        time += 1
        disc[u] = low[u] = time

        for v in graph[u]:
            if not visited[v]:
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])

                # Bridge condition statement ( if im not mistaken)
                if low[v] > disc[u]:
                    bridges.append((u, v))

            elif v != parent[u]:
                # Back edge
                low[u] = min(low[u], disc[v])

    dfs(0)
    return bridges

# correctness proof
Base Case:
if vertex u has no parent, then low[v] > disc[v] MUST be tree meaning u,v is correctly marked as a bridge.
Inductive Hypothesis:
Assume that for every enode x whose DFS call finishes before we begin processing node u, the algorithm has already correctly computed its discovyer time, lowest reachable ancestor, and identified every bridge to the subtree rooted at x. from low[child] > disc[parent]
**Ill perform a DFS and track 2 values for each node.**
* disc[u] is the timestamp when u is first visited
* low[u] is the smallest discovery time reachable from u using DFS tree edges and at most 1 back edge.

**For any tree edge (u,v) in the DFS tree:**
* If low[v] > disc[u] then v CANT reach any ancestory of u via a back edge.
* therefore removing (u,v) disconnects the subtree rooted at v from the rest of the graph.
* hence (u,v) MUSt be a bridge.

# time complexity
**Time**
The time will be O(V + E)
This is because DFS runs in linear time, each edge is processed a constant number of times, and all updates done are O(1) so they don't exceed the cost.
**This algorithm runs in linear time. **