# [Critical Connections in a Network](https://leetcode.com/problems/critical-connections-in-a-network/)

### Parent Problem:
Find the bridge in the given graph.

### Solution Approach
We'll be using targen's Bridge finding algorithm here, the idea is to mark discuvery time and earliest (smallest) reachable node's discovery time(low time) for a particular node.

* If any neighbour of the given node can not be discuvered earlier than this node, (parent node chhod k) then this edge is an bridge or critical point.

### Example Walthough

Lets take an example of the following graph:-

0------1
| \
| \
| \
| \
5----3-------2
|
|
4

A bridge is simply an edge in an undirected connected graph reoving which disconnects the graph.
To find all the bridges in the graph we perform a dfs to visit each node.
While we visit each node we assign two values to it Disc time number and lowlink number.

Disc time - Denotes the time at which the node is visited.
Low number - Denotes whether there is other early node(based on Disc time number) that can be visited by that node.

(disc=1,
low=1)
|
0------1
| \
| \
| \
| \
5----3-------2
|
|
4

(Disc=1,
low=1)
|
0------1 <----(Disc=2,low=2)
| \
| \
| \
| \
5----3-------2
|
|
4

(Disc=1,
low=1)
|
0------1 <----(Disc=2,low=2)
| \
| \
| \
| \
5----3-------2 <----(Disc=3,low=3)
|
|
4

(Disc=1,
low=1)
|
0------1 <----(Disc=2,low=2)
| \
| \
| \
|(Disc=4,ll=4)\
5----3-------2 <----(Disc=3,low=3)
|
|
4

(Disc=1,
low=1)
|
0------1 <----(Disc=2,low=2)
| \
| \
| \
|(Disc=4,ll=4)\
5----3-------2 <----(Disc=3,low=3)
|
|
4
|
(Disc=5,low=5)

Since there are no unvisited nodes to node 4 we have to check 2 things while cosidering 3(parent) and 4(node):-

1. Compare the low values of 3 and 4 and assign the minimum value to 3(Since the low value of 3 and 4 minimum is 3 we dont do anything).

Why did we do this?
We needed to compare the lowlink values of both nodes to update the information of nodes 3s connectivity to the earliest node possible.

2. We compare the low value of 4 and Disc value of 3.This will decide whether this edge is a bridge or not.
As the Disc value of 3 is lesser than the low value of 4 we can safely say that node 4 has no connections with nodes which where made at earlier time.
Thus 3-4 is a bridge.

Note that 1 and 2 are if else cases if low[node]<=low[neighbor] then perform 1
else perform 2

(Disc=1,
low=1)
|
0------1 <----(Disc=2,low=2)
| \
| \
| \
|(Disc=4,ll=4)\
(Disc=6,low=6)---> 5----3-------2 <----(Disc=3,low=3)
|
|
4
|
(Disc=5,low=5)

Then perform the same operations with the other nodes.

# Code

class Solution {
public:
    int timer;
    void dfs(vector<int>&low,vector<int>&disc,int node, int parent,vector<vector<int>>&graph,vector<vector<int>>&ans){
        low[node]=disc[node]=timer++;
        for(int nbr:graph[node]){
            if(nbr==parent)
                continue;
            if(disc[nbr]==0)
                dfs(low,disc,nbr,node,graph,ans);
            low[node]=min(low[node],low[nbr]);
            
            if(low[nbr]>disc[node]){
                ans.push_back({node,nbr});
            }
        }
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<int>disc(n,0),low(n,0);
        vector<vector<int>>graph(n),ans;
        timer=1;
        for(vector<int> conc:connections){
            graph[conc[0]].push_back(conc[1]);
            graph[conc[1]].push_back(conc[0]);
        }
        dfs(low,disc,0,-1,graph,ans);
        return ans;
    }
};