1192. Critical Connections in a Network

https://leetcode.com/problems/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] = [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.

图上一条边如果去掉后会导致有些点不可达，则称该边为critical path，让找图上所有的critical paths。当图上的边形成一个环，环上任何一条边都不会是critical path，并且不在环上的边都是critical path。图上找出所有的环用一遍DFS，对每个遇到的点记录下level，并让每个DFS call 返回从它往后能遇到的最小的level。当返回最小的level比父节点level还小时，意味着父节点前面的结点能被它的子节点再访问到，也就是形成了环。

/*
 * @lc app=leetcode id=1192 lang=cpp
 *
 * [1192] Critical Connections in a Network
 */

// @lc code=start
class Solution {
public:
    int dfs(unordered_map<int, vector<int>> &edges, int cur, int par, int level, vector<int> &ms, vector<vector<int>> &res) {
        ms[cur] = level;
        for (const auto nei : edges[cur]) {
            if (nei == par) continue;
            if (ms[nei] != INT_MAX) {
                ms[cur] = min(ms[cur], ms[nei]);
                continue;
            } 
            ms[cur] = min(ms[cur], dfs(edges, nei, cur, level + 1, ms, res));
        }
        if (ms[cur] == level && cur != 0) res.push_back({par, cur});
        return ms[cur];
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        unordered_map<int, vector<int>> edges;
        for (const auto &c : connections) {
            edges[c[0]].push_back(c[1]);
            edges[c[1]].push_back(c[0]);
        } 
        vector<int> ms(n, INT_MAX);
        vector<vector<int>> res;
        dfs(edges, 0, -1, 0, ms, res);
        return res;
    }
};
// @lc code=end