## Critical Connections in a Network

####
*This is a draft post.*

*January 2021*

**Problem #1192, LeetCode**

There are `n`

servers numbered from `0`

to `n-1`

connected by undirected server-to-server connections forming a network where `connections[i] = [a, b]`

represents a connection between servers `a`

and `b`

. Any server can reach any other server directly or indirectly through the network.

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

Return all critical connections in the network in any order.

Example 1:

Input: `n = 4`

, `connections = [[0,1],[1,2],[2,0],[1,3]]`

Output: `[[1,3]]`

Explanation: `[[3,1]]`

is also accepted.

Constraints:

```
1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.
```

Accepted 93,286 Submissions 186,676

**Solution**

First thought that came to my mind was to do a node discovery
runs on each of the nodes. The search will give a list of
redundant path, which we can use to determine non-critical
connections. Repeat this for `n`

nodes, and pick the connections
that are not non-critical.

Glad it was the first thought and not the solution! Because it is convoluted and I’m not even sure if it will yield the desired output.

Now, the second thought is to iterate over the `connections`

array. Since we are to find whether the given connection is
critical, we can try removing that connection from the graph and
test if the reachability is still the same.

For this we can run a graph searching algorithm - BFS/DFS/etc - from either of the nodes that the deleted connection contains. If we find the other node from the search, then the reachability is still the same. This is due to the fact that, however convoluted, any path that utilized the deleted connection now can use the newly found path between the two nodes.

Todo:

- Complexity calculation

*Tags:
coding challenges
draft
*