# 1192. Critical Connections in a Network / Find Bridges

## Problem Statement

\


There are `n` servers numbered from `0` to `n - 1` connected by undirected server-to-server `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between servers `ai` and `bi`. Any server can reach other servers directly or indirectly through the network.

A _critical connection_ is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/09/03/1537_ex1_2.png)

<pre><code><strong>Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
</strong><strong>Output: [[1,3]]
</strong><strong>Explanation: [[3,1]] is also accepted.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: n = 2, connections = [[0,1]]
</strong><strong>Output: [[0,1]]
</strong></code></pre>

&#x20;

**Constraints:**

* `2 <= n <= 105`
* `n - 1 <= connections.length <= 105`
* `0 <= ai, bi <= n - 1`
* `ai != bi`
* There are no repeated connections.

## Intuition

```
Approach:

Maintain two arrays , start time and low(tracking lowest timre it can reach)
Traverse,

Whenever the low[adjacent node] > starttime[parent]  
    Bridge

Intuition is that,
    2
  /  \
1 ----3 -- 4
(start_time, low)
We start Dfs from 1(1,1) -> 2(2,2) -> 3(3,3) -> 2
Now we reach 2 but dfs over here, we update low of 3
Lowest 3 can be reach 2
3(3,2) -> 4(4,4)
Now low(4) > start[3] hence, it means 4 was visited at time 4
But 3 was visited at strating 3, can hence 4 cannot reach 3, hence bridge


```

### Links

[https://leetcode.com/problems/critical-connections-in-a-network/description/](https://leetcode.com/problems/critical-connections-in-a-network/description/)

### Video Links

[https://www.youtube.com/watch?v=qrAub5z8FeA](https://www.youtube.com/watch?v=qrAub5z8FeA)

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
class Solution {
public:
    int timer=1;
    vector<vector<int>> bridges;
    vector<int> start, low;
    void dfs(int node, int parent, vector<bool> &visited, vector<int> adj[]){
        visited[node] = true;
        start[node] = timer;
        low[node] = timer;
        timer++;

        for(auto &it: adj[node]){
            if(it == parent)   
                continue;

            if(!visited[it]){
                dfs(it, node, visited, adj);
                low[node] = min(low[node], low[it]);
                if(low[it] > start[node])
                    bridges.push_back({it,node});

            }
            else{
                low[node] = min(low[node], low[it]);
            }
        } 
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<int> adj[n];
        start.resize(n);
        low.resize(n);
        vector<bool> visited(n, false);

        for(auto &it: connections){
            adj[it[0]].push_back(it[1]);
            adj[it[1]].push_back(it[0]);
        }

        dfs(0, -1, visited, adj);
        return bridges;
    }
};
```
{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}
```cpp
```
{% endcode %}

### Similar Problems

###

