Java | Solved using Tarjan but why!!
I solved this problem (somehow) by going googling for algorithm to detect bridges in a graph and then translating it myself to code. But I had a basic question 
I solved this problem (somehow) by going googling for algorithm to detect bridges in a graph and then translating it myself to code. But I had a basic question while working on it. What does this question expect ??\n\n1. Be able to discover Tarjan\'s alorithm all by yourself in an interview setting with limited time and all the while explaining your thought process to the interviewer.\n2. Already know a standard algorithm (like Tarjan\'s) to solve this type of problem.\n\nOf the 2 options above, for option#1, perhaps you need to be an out-of-the world genius (perhaps in league with Robert Tarjan or Kosaraju themselves). And for option#2, you need to be plain lucky to get a question on an algo which you just happen to remember.\n\nIn either case, I do not think this question is a good example of an interview question. Neverthelss it has got 2K+ thumbs up on leetcode, but surely don\'t count be amongst them.\n\nOk, now enough of ranting. Here\'s a java solution I put together after going through a few videos explaining bridge detection algorithms for a graph.\n\n```\nclass Solution {\n        int time = 0;\n    List<List<Integer>> result;\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        result = new ArrayList<>();\n        int[] parents = new int[n];\n        int[] times = new int[n];\n        ArrayList<Integer>[] adj = new ArrayList[n];\n        Set<Integer> visited = new HashSet<>();\n\n        for(List<Integer> connection : connections) {\n            if(adj[connection.get(0)] == null) {\n                adj[connection.get(0)] = new ArrayList<>();\n            }\n            adj[connection.get(0)].add(connection.get(1));\n\n            if(adj[connection.get(1)] == null) {\n                adj[connection.get(1)] = new ArrayList<>();\n            }\n            adj[connection.get(1)].add(connection.get(0));\n        }\n\n        for(int i = 0; i < n; i++) {\n            if(!visited.contains(i)) {\n                dfs(i, -1, adj, parents, times, visited);\n            }\n        }\n        return result;\n    }\n\n    private void dfs(int node, int parent, ArrayList<Integer>[] adj, int[] parents, int[] times, Set<Integer> visited) {\n        visited.add(node);\n        times[node] = time;\n        time++;\n        if(adj[node] != null) {\n            for(int i : adj[node]) {\n                if(!visited.contains(i)) {\n                    dfs(i, node, adj, parents, times, visited);\n                }\n            }\n\n            if(parent > - 1) {\n                int min = times[node];\n                for(int i : adj[node]) {\n                    if(i != parent && times[i] <= times[parent]) {\n                        min = Math.min(min, times[i]);\n                    }\n                }\n                times[node] = min;\n                if(min <= times[parent]) {\n                    return;\n                } else {\n                    List<Integer> bridge = new ArrayList<>();\n                    bridge.add(parent);\n                    bridge.add(node);\n                    result.add(bridge);\n                }\n            }\n        }\n    }\n}\n```\n\n
[]