Java - Best Explained - Simple and Concise - DFS Solution
Intuition -\nAn edge (u,v) will be a critical connection, if to reach node v in the network we\'ve only node u, i.e. if we start visiting nodes from a source ve
**Intuition -**\nAn edge (u,v) will be a critical connection, if to reach node **v** in the network we\'ve only node **u**, i.e. if we start visiting nodes from a source vertex 0 using DFS, and keep assigning discovery time to each time, while checking if it can be visited earlier from any alternate route. If it\'s possible to visit a node  earlier from different route, than this node cannot be a bridge/critical connection. \n\nIf it\'s node possible to visit a node **v** earlier from a different route than the current parent node **u**, then the edge (u,v) is critical connection.\n\nFollow the comments in the code to understand it better and let me know if further explaination is required. "Upvote" if you liked this post \uD83D\uDE0A\n\n```\nclass Solution {\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        // Prepare the adjaceny list from the given edges \n        ArrayList<ArrayList<Integer>> adjList = createAdjacenyList(n, connections);\n        \n        // Stores critical edges/answer\n        List<List<Integer>> ans = new ArrayList();\n        \n        // Stores discovery time and minimum discovery time of each node in the graph\n        int[] dis = new int[n];\n        int[] minDis = new int[n];\n        \n        // Running timer, starts from 1.\n        int[] timer = new int[] { 1 };\n        \n        // DFS from 0th node, since there is no parent, set parent to -1.\n        dfs(0, -1, adjList, dis, minDis, timer, ans);\n        \n        return ans;\n    }\n    \n    private ArrayList<ArrayList<Integer>> createAdjacenyList(int n, List<List<Integer>> edges) {\n        ArrayList<ArrayList<Integer>> adjList = new ArrayList();\n        \n        for(int i=0; i<n; i++)\n            adjList.add( new ArrayList() );\n        \n        for(List<Integer> edge : edges) {\n            int u = edge.get(0);\n            int v = edge.get(1);\n            adjList.get( u ).add( v );\n            adjList.get( v ).add( u );\n        }\n        \n        return adjList;\n    }\n    \n    private void dfs(int node, int parent, ArrayList<ArrayList<Integer>> adjList, int[] dis, int[] minDis, \n                     int[] timer, List<List<Integer>> ans) {\n\n        // Set minimum discovery time and discovery time to current time\n        minDis[node] = dis[node] = timer[0]++;\n        \n        for(int adj : adjList.get(node)) {\n            // Skip if the adjacent node is the parent\n            if( adj == parent ) \n                continue;\n            \n            // If adjacent node is not yet visited, DFS on the adjacent node\n            if( dis[adj] == 0 ) \n                dfs(adj, node, adjList, dis, minDis, timer, ans);\n            \n            /* If adjacent node can be discovered early than the current node, \n            than update the minimum discovery time of current node as well */\n            minDis[node] = Math.min(minDis[node], minDis[adj]);\n        }\n        \n        /* If current node can only be disovered from the parent node, than the\n        parent to current node\'s edge is critical edge (bridge) */\n        if( parent != -1 && minDis[node] > dis[parent] ) \n            ans.add( new ArrayList() {{ add(parent); add(node); }});\n    }\n}\n```
['Java']