golang 解法, 执行用时: 356 ms, 内存消耗: 36.2 MB, 提交时间: 2023-10-07 11:22:15

func criticalConnections(n int, connections [][]int) [][]int {
    // 建图
    m := make(map[int][]int)
    for _, c := range connections {
        m[c[0]] = append(m[c[0]], c[1])
        m[c[1]] = append(m[c[1]], c[0])
    }

    res := [][]int{}
    id := make([]int, n)
    for i := range id {
        id[i] = -1
    }
    // tarjan 思路 不断给节点标记id值(发现的先后顺序)， 遇到环就把换上节点统一到小值
    var dfs func(node, curId, perv int) int
    dfs = func(node, curId, perv int) int {
        id[node] = curId

        for _, next := range m[node] {
            if next == perv {
                continue
            }
            if id[next] == -1 {
                id[node] = min(id[node], dfs(next, curId+1, node))
            } else {
                id[node] = min(id[node], id[next])
            }
        }

        if id[node] == curId && node != 0 {
            res = append(res, []int{perv, node})
        }

        return id[node]
    }
    dfs(0, 0, -1)

    return res
}


func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

cpp 解法, 执行用时: 956 ms, 内存消耗: 240.6 MB, 提交时间: 2023-10-07 11:21:24

class Solution {
public:
    void buildMap(const vector<vector<int>>& connections, unordered_map<int, unordered_set<int>>& hm){
        for(auto& connection: connections){
            int nodeA = connection[0];
            int nodeB = connection[1];

            hm[nodeA].emplace(nodeB);
            hm[nodeB].emplace(nodeA);
        }
    }

    int dfs(int node, int nodeID, int parent, vector<int>& id, unordered_map<int, unordered_set<int>>& hm, vector<vector<int>>& ans){
        id[node] = nodeID;

        for(int neighbor: hm[node]){
            if(neighbor == parent) continue;
            else if(id[neighbor] == -1){
                id[node] = min(id[node], dfs(neighbor, nodeID + 1, node, id, hm, ans));
            }else{
                id[node] = min(id[node], id[neighbor]);
            }
        }

        if(id[node] == nodeID && node != 0){
            ans.push_back({parent, node});
        }
        return id[node];
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        unordered_map<int, unordered_set<int>> hm;
        vector<int> id(n, -1);
        vector<vector<int>> ans;

        buildMap(connections, hm);

        dfs(0, 0, -1, id, hm, ans);
        return ans;
    }
    
};

java 解法, 执行用时: 263 ms, 内存消耗: 145 MB, 提交时间: 2023-10-07 11:21:01

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // 构建一个map，存放每个节点的相邻节点有哪些
        Map<Integer, Set<Integer>> map = new HashMap<>();
        buildMap(connections, map);
        
        // 创建一个数组，存放每个节点的id是什么
        int[] id = new int[n];
        Arrays.fill(id, -1);
        
        // 选取一个点作为根节点，dfs向下递归，过程中识别出哪个边是critical connection
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, 0, -1, id, map, res);    // 假设根节点有一个编号是-1父节点
        
        return res;
    }
    
    public int dfs(int node, int nodeID, int par, int[] id, Map<Integer, Set<Integer>> map, List<List<Integer>> res){
        id[node] = nodeID;
        
        Set<Integer> set = map.get(node);
        for(Integer neighbor: set){
            if(neighbor == par){
                continue;
            }else if(id[neighbor] == -1){
                id[node] = Math.min(id[node], dfs(neighbor, nodeID + 1, node, id, map, res));
            }else{
                id[node] = Math.min(id[node], id[neighbor]);
            }
        }
        
        if(id[node] == nodeID && node != 0){
            res.add(Arrays.asList(par, node));
        }
        
        return id[node];
    }
    
    public void buildMap(List<List<Integer>> con, Map<Integer, Set<Integer>> map){
        for(List<Integer> edge : con){
            int n1 = edge.get(0);
            int n2 = edge.get(1);
            
            Set<Integer> n1n = map.getOrDefault(n1, new HashSet<>());
            Set<Integer> n2n = map.getOrDefault(n2, new HashSet<>());
            
            n1n.add(n2);
            n2n.add(n1);
            
            map.put(n1, n1n);
            map.put(n2, n2n);
        }
    }
}

python3 解法, 执行用时: 588 ms, 内存消耗: 71.2 MB, 提交时间: 2023-10-07 11:20:49

# dfs + tarjan 算法
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # 建图
        graph = collections.defaultdict(list)
        for conn in connections:
            graph[conn[0]].append(conn[1])
            graph[conn[1]].append(conn[0])

        # 建id
        ids = [-1] * n

        # 建返回
        res = []

        # 定义深度优先
        def dfs(cur_node, cur_id, par):
            # 在探索之前，给你个id
            ids[cur_node] = cur_id
            
            # 探索相邻节点
            for next_node in graph[cur_node]: # 寻找相邻节点
                if next_node == par: # 忽略自己
                    continue
                elif ids[next_node] == -1:  # 相邻不知道，深度，并取最小
                    ids[cur_node] = min(dfs(next_node,cur_id+1,cur_node),ids[cur_node])
                else: # 相邻有，取最小
                    ids[cur_node] = min(ids[cur_node],ids[next_node])

            # 整理完的最终id == cur_id（上面传进来的）
            # 是环的脑袋
            # 另外不要忘记 排除特殊
            if ids[cur_node] == cur_id and cur_node != 0:
                res.append((par,cur_node))
            return ids[cur_node]
        
        dfs(0,0,-1)
        return res