0% completed
Problem Statement
You are given n
servers numbered from 0
to n-1
, connected by some number of undirected connections 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 servers.
Return all critical connections in the network.
Examples
Example 1:
- Input: n = 5, connections =
[[0, 1], [1, 2], [2, 3], [3, 4], [2, 4]]
- Expected Output:
[[1,2],[0,1]]
- Justification: Removing either
[0, 1]
or[1, 2]
will split the network into separate parts, making some servers unreachable from others.
Example 2:
- Input: n = 4, connections =
[[0, 1], [0, 2], [1, 2], [2, 3]]
- Expected Output:
[[2, 3]]
- Justification: Removing
[2, 3]
will isolate server3
, making it unreachable from the other servers.
Example 3:
- Input: n = 6, connections =
[[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]]
- Expected Output:
[[1, 3]]
- Justification: Removing
[1, 3]
will disconnect servers3
,4
, and5
from the rest of the network.
Constraints:
- 2 <= n <= 10<sup>5</sup>
- n - 1 <= connections.length <= 10<sup>5</sup>
- 0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1
- a<sub>i</sub> != b<sub>i</sub>
- There are no repeated connections.
Solution
To solve this problem, we can use Depth First Search (DFS). The key idea is to identify bridges in the graph. A bridge is an edge that, when removed, splits the graph into disconnected parts. By using DFS, we can record the discovery and low-link values of each node. The discovery time is the time at which a node is first visited, and the low-link value is the smallest discovery time reachable from the node. If a node cannot reach an ancestor node through its descendants, then the edge leading to that descendant is a critical connection.
This approach is effective because it systematically explores all nodes and edges using DFS, ensuring that all potential critical connections are examined. The use of discovery and low-link values helps in efficiently identifying critical connections with a time complexity of O(V + E), where V is the number of nodes and E is the number of edges.
Step-by-Step Algorithm
-
Initialize Data Structures:
- Create an adjacency list
graph
to represent the network of servers. - Create arrays
disc
andlow
to store the discovery times and the lowest discovery times reachable for each node, initialized to-1
. - Initialize a list
res
to store the critical connections. - Set a global
time
variable to track the discovery time during DFS.
- Create an adjacency list
-
Build the Graph:
- For each connection
[u, v]
inconnections
, addv
to the adjacency list ofu
andu
to the adjacency list ofv
.
- For each connection
-
DFS Function:
- Define a recursive DFS function that takes the current node
u
, its parent nodeparent
, thedisc
,low
,graph
, andres
as arguments. - Set
disc[u]
andlow[u]
to the currenttime
, then incrementtime
. - For each neighbor
v
ofu
in the graph:- If
v
is the parent ofu
, skip it. - If
v
has not been visited (disc[v] == -1
):- Recursively call DFS on
v
withu
as the parent. - Update
low[u]
to the minimum oflow[u]
andlow[v]
. - If
low[v] > disc[u]
, add[u, v]
tores
as it is a critical connection.
- Recursively call DFS on
- If
v
has already been visited and is not the parent, updatelow[u]
to the minimum oflow[u]
anddisc[v]
.
- If
- Define a recursive DFS function that takes the current node
-
Run DFS:
- Call the DFS function starting from node
0
with-1
as the parent.
- Call the DFS function starting from node
-
Return Result:
- Return the list
res
containing all the critical connections.
- Return the list
Algorithm Walkthrough
Let's walk through the algorithm with n = 5
and connections = [[0, 1], [1, 2], [2, 3], [3, 4], [2, 4]]
.
-
Initialize Data Structures:
graph = [[], [], [], [], []]
disc = [-1, -1, -1, -1, -1]
low = [-1, -1, -1, -1, -1]
res = []
time = 0
-
Build the Graph:
- After processing
connections
:graph = [[1], [0, 2], [1, 3, 4], [2, 4], [3, 2]]
- After processing
-
Run DFS starting from node 0:
-
DFS on node 0:
disc[0] = 0
,low[0] = 0
,time = 1
- Visit neighbor
1
.
-
DFS on node 1:
disc[1] = 1
,low[1] = 1
,time = 2
- Skip neighbor
0
(parent). - Visit neighbor
2
.
-
DFS on node 2:
disc[2] = 2
,low[2] = 2
,time = 3
- Skip neighbor
1
(parent). - Visit neighbor
3
.
-
DFS on node 3:
disc[3] = 3
,low[3] = 3
,time = 4
- Skip neighbor
2
(parent). - Visit neighbor
4
.
-
DFS on node 4:
-
disc[4] = 4
,low[4] = 4
,time = 5
-
Skip neighbor
3
(parent). -
Visit neighbor
2
. -
Node 2 has been visited already, and it's not the parent of node 4. Update
low[4] = min(low[4], disc[2]) = min(4, 2) = 2
.
-
-
Backtrack to node 3:
low[3] = min(low[3], low[4]) = min(3, 2) = 2
.low[4] > disc[3]
is not true (2 > 3
is false). So[3, 4]
is not a critical connection.
-
Backtrack to node 2:
low[2] = min(low[2], low[3]) = min(2, 2) = 2
.-
Visit neighbor
4
again. -
Node 4 has been visited already, and it's not the parent of node 2. Update
low[2] = min(low[2], disc[4]) = min(2, 4) = 2
. -
Backtrack to node 1:
low[1] = min(low[1], low[2]) = min(1, 2) = 1
. -
low[2] > disc[1]
is true (2 > 1
is true). So[1, 2]
is a critical connection. Add[1, 2]
tores
.
-
-
Backtrack to node 0:
low[0] = min(low[0], low[1]) = min(0, 1) = 0
.low[1] > disc[0]
is true (1 > 0
is true). So[0, 1]
is a critical connection. Add[0, 1]
tores
.
-
-
Result:
res = [[1, 2], [0, 1]]
.
The final result is [[1, 2], [0, 1]]
, meaning removing either of these connections will split the network into separate parts.
Code
Complexity Analysis
Time Complexity: The algorithm runs in O(V + E) time, where V is the number of vertices (servers) and E is the number of edges (connections). This is because we perform a DFS traversal of the graph, visiting each vertex and edge once.
Space Complexity: The space complexity is O(V + E) due to the storage required for the graph representation and the recursion stack used by the DFS algorithm.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible