Leetcode 1192: Cirtical 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 <= 10^5
• n - 1 <= connections.length <= 10^5
• 0 <= ai, bi <= n - 1
• ai != bi
• There are no repeated connections.

Problem Analysis:

It is a graphic problem. We can think that if there is a cycle, the edges in the cycle are not critical connections, as we delete any one edge in the cycle, all nodes in the cycle are still connecting, and for nodes out of the cycle, it is still connecting. So only if an edge is not in a cycle, it is a critical connection.

So our destination can change to find all edges that can not be a part of a cycle.

As all nodes can connect in the network, we can use depth search first algorithm, we iterate searching nodes starting from node a, through its edges, we find its neighbors, and neighbors’ neighbors, …

If some node can not iterate the node that we previous iterating, the pair of node and previous node form one critical connection.

Solution

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> graph(n);
        for (const auto& item: connections) {
            graph[item[0]].push_back(item[1]);
            graph[item[1]].push_back(item[0]);
        }

        vector<int> rank(n, -2);
        vector<vector<int>> res;
        help(graph, n, 0, 0, rank, res);

        return res;
    }

    int help(vector<vector<int>>& graph, int n, int node, int myRank, vector<int>& rank, vector<vector<int>>& res) {
        if (rank[node] != -2) return rank[node];

        int lowestRank{myRank};
        rank[node] = myRank;
        for (const auto& item: graph[node]) {
            if (rank[item] == myRank - 1 || rank[item] == n) continue;
            int neighborRank = help(graph, n, item, myRank + 1, rank, res);
            lowestRank = min(lowestRank, neighborRank);
            if (neighborRank > myRank) res.push_back({min(node, item), max(node, item)});
        }

        rank[node] = n;
        return lowestRank;
    }
};

Time complexity is O(number of edges)

Space complexity is O(max(number of edges), n)