1192. Critical Connections in a Network

 一刷 07/2022

Version #1 DFS with node rank

一开始想到了是要求cycle，但是没有想到怎么把cycle里面的edge记录下来

看答案学习了这个rank的方法，是以前从来没有遇到过的，狠狠记住

Time O(E + V)

Space O(E + V)

Runtime: 311 ms, faster than 25.27% of Java online submissions for Critical Connections in a Network.

Memory Usage: 372.1 MB, less than 8.95% of Java online submissions for Critical Connections in a Network.

class Solution {

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {

        // If an edge is part of a cycle, then it is not a critical connection

        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            graph.add(new ArrayList<>());

        }

        for (List<Integer> conn : connections) {

            int node1 = conn.get(0);

            int node2 = conn.get(1);

            graph.get(node1).add(node2);

            graph.get(node2).add(node1);

        }

        Set<List<Integer>> nonCriticalConn = new HashSet<>();

        dfs(graph, 0, nonCriticalConn, 0, new HashMap<>());

        List<List<Integer>> result = new ArrayList<>();

        for (List<Integer> conn : connections) {

            Collections.sort(conn);

            if (nonCriticalConn.contains(conn)) {

                continue;

            }

            result.add(conn);

        }

        return result;

    }

    

    private int dfs(List<List<Integer>> graph, int node, Set<List<Integer>> nonCriticalConn, int rank, Map<Integer, Integer> ranks) {

        // assign rank + 1 to all the neighbors

        // if a neighbor already has a rank smaller than current rank, it means the neighbor has been visited

        // return the min rank of all neighbors recursively

        if (ranks.containsKey(node)) {

            return ranks.get(node);

        }

        ranks.put(node, rank);

        int minRank = rank;

        for (int next : graph.get(node)) {

            Integer nextRank = ranks.get(next);

            // skip the parent

            if (nextRank != null && nextRank == rank - 1) {

                continue;

            }

            nextRank = dfs(graph, next, nonCriticalConn, rank + 1, ranks);

            if (nextRank <= rank) {

                nonCriticalConn.add(new ArrayList<>(Arrays.asList(new Integer[]{Math.min(node, next), Math.max(node, next)})));

                minRank = Math.min(minRank, nextRank);

            }

        }

        return minRank;

    }

}