Critical Connections in a Network | Tarjan's Algorithm | Explanation & Comments
Explanation:\n=\nStep 1: The graph is created from a hashmap and populated with the concerned values from the connections list of lists variable.\n\nStep 2: A l
Explanation:\n=\nStep 1: The graph is created from a hashmap and populated with the concerned values from the connections list of lists variable.\n\nStep 2: A list of list variable named ans is initialized to store the vertices combination which are critical connections.\n\nStep 3: An array variable rank is created to store the rank of the corresponding indices(i.e.., vertices) and initialized. (rank: According to Graph theory it is a difference between number of vertices and the connected components).\n\nStep 4: A boolean array is created to check the visited vertices.\n\nStep 5: A variables preNode, curNode and curRank are declared and initialized to -1, 0 and 0 respectively.(Since the dfs will be started with the 0 as current node with rank of the current node as 0 and the previous node will be obviously -1).\n\nStep 6: The dfs is invoked and inside it the visited array and rank array for the current node will be updated.\n\nStep 7: Then the for loop iterates towards the graph for the neighbours of the current node via a graph. If the current node is the previous node then the iteration is skipped.\n\nStep 8: Then the dfs is again invoked with current node as a previous node and the current neighbour as a current node with current rank value incremented by 1.\n\nStep 9: Then from step 7 if the node is already visited then the minimum rank value of it in comparison with the neighbor node is considered.\n\nStep 10: Then if the rank of the neighbor is less than the rank of the current vertice then it means the current node is critically connected. Then the current node along with its neighbor to which its critically connected is added to the ans list.\n\nSolution:\n=\n```\nclass Solution \n{\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) \n    {\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        List<List<Integer>> ans = new LinkedList<>();\n        for (List<Integer> connection : connections)\n        {\n            int a = connection.get(0);\n            int b = connection.get(1);\n            graph.putIfAbsent(a, new LinkedList<>());\n            graph.putIfAbsent(b, new LinkedList<>());\n            graph.get(a).add(b);\n            graph.get(b).add(a);\n        }\n        int[] rank = new int[n];\n        for (int i = 0; i < n; ++i)\n        {\n            rank[i] = i;\n        }\n        boolean[] visited = new boolean[n];\n        int prevNode = -1, curNode = 0, curRank = 0;\n        dfs(visited, rank, prevNode, curNode, curRank, graph, ans);\n        return ans;\n    }\n    \n    private void dfs(boolean[] visited, int[] rank, int prevNode, int curNode, int curRank, Map<Integer, List<Integer>> graph, List<List<Integer>> ans)\n    {\n        rank[curNode] = curRank;\n        visited[curNode] = true;\n        for (int neighbor : graph.get(curNode))\n        {\n            if (neighbor == prevNode)\n                continue;\n            if (!visited[neighbor])\n                dfs(visited, rank, curNode, neighbor, curRank + 1,graph,ans);\n            rank[curNode] = Math.min(rank[curNode], rank[neighbor]);\n            if (rank[neighbor] == curRank + 1){\n                ans.add(Arrays.asList(curNode, neighbor));\n            }\n        }\n    }\n}\n```\n\n<b>Thanks & Regards,\nHariprasath N.<b>
['Depth-First Search', 'Java']