1192. Critical Connections in a Network LeetCode Solution

In this guide, you will get 1192. Critical Connections in a Network LeetCode Solution with the best time and space complexity. The solution to Critical Connections in a Network problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Critical Connections in a Network solution in C++
  4. Critical Connections in a Network solution in Java
  5. Critical Connections in a Network solution in Python
  6. Additional Resources
1192. Critical Connections in a Network LeetCode Solution image

Problem Statement of Critical Connections in a Network

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.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

Constraints:

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

1192. Critical Connections in a Network LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> criticalConnections(int n,
                                          vector<vector<int>>& connections) {
    vector<vector<int>> ans;
    vector<vector<int>> graph(n);

    for (const vector<int>& connection : connections) {
      const int u = connection[0];
      const int v = connection[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    // rank[i] := the minimum node that node i can reach with forward edges
    // Initialize with NO_RANK = -2 to indicate not visited.
    getRank(graph, 0, 0, vector<int>(n, NO_RANK), ans);
    return ans;
  }

 private:
  static constexpr int NO_RANK = -2;

  // Gets the minimum rank that u can reach with forward edges.
  int getRank(const vector<vector<int>>& graph, int u, int currRank,
              vector<int>&& rank, vector<vector<int>>& ans) {
    if (rank[u] != NO_RANK)  // The rank is already determined.
      return rank[u];

    rank[u] = currRank;
    int minRank = currRank;

    for (const int v : graph[u]) {
      // visited || parent (that's why NO_RANK = -2 instead of -1)
      if (rank[u] == rank.size() || rank[v] == currRank - 1)
        continue;
      const int nextRank =
          getRank(graph, v, currRank + 1, std::move(rank), ans);
      // (u, v) is the only way for u go to v.
      if (nextRank == currRank + 1)
        ans.push_back({u, v});
      minRank = min(minRank, nextRank);
    }

    rank[u] = rank.size();  // Mark as visited.
    return minRank;
  }
};
/* code provided by PROGIEZ */

1192. Critical Connections in a Network LeetCode Solution in Java

class Solution {
  public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (List<Integer> connection : connections) {
      final int u = connection.get(0);
      final int v = connection.get(1);
      graph[u].add(v);
      graph[v].add(u);
    }

    // rank[i] := the minimum node that node i can reach with forward edges
    // Initialize with NO_RANK = -2 to indicate not visited.
    int[] rank = new int[n];
    Arrays.fill(rank, NO_RANK);
    getRank(graph, 0, 0, rank, ans);
    return ans;
  }

  private static final int NO_RANK = -2;

  // Gets the minimum rank that u can reach with forward edges.
  private int getRank(List<Integer>[] graph, int u, int myRank, int[] rank,
                      List<List<Integer>> ans) {
    if (rank[u] != NO_RANK) // The rank is already been determined.
      return rank[u];

    rank[u] = myRank;
    int minRank = myRank;

    for (final int v : graph[u]) {
      // visited || parent (that's why NO_RANK = -2 instead of -1)
      if (rank[u] == rank.length || rank[v] == myRank - 1)
        continue;
      final int nextRank = getRank(graph, v, myRank + 1, rank, ans);
      // (u, v) is the only way for u go to v.
      if (nextRank == myRank + 1)
        ans.add(Arrays.asList(u, v));
      minRank = Math.min(minRank, nextRank);
    }

    rank[u] = rank.length; // Mark as visited.
    return minRank;
  }
}
// code provided by PROGIEZ

1192. Critical Connections in a Network LeetCode Solution in Python

N/A
# code by PROGIEZ

Additional Resources

See also  686. Repeated String Match LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.