Java Solution Kosaraju's Algorithm + Tarjan's Algorithm
Kosaraju\'s AlgorithmComplexity: O(V+E)\nTwo DFS Traversal\n\n The idea is to apply Kosaraju\'s algorithm to get the strongly connected components\n In first DF
**Kosaraju\'s Algorithm**`Complexity: O(V+E)`\n*Two DFS Traversal*\n\n* The idea is to apply Kosaraju\'s algorithm to get the strongly connected components\n* In first DFS we get the order of the traversal of nodes\n* A slight improvement which can be done here is that instead of taking transpose of the graph(Since this is undirected graph) just remove the edge from the parent\n* Now while doing the 2nd dfs whenever we pop from stack and visit it means we have encountered a new strongly connected component. So we add this edge as a critical connection. Note here that for the first time `parent[v] = -1` so we dont have to add.\n* Benefits of using this algorithm is its fairly simple to understand than Tarjan\'s algorithm\n\n\n\n```\nclass Solution {\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        List<Set<Integer>> adj = new ArrayList<>();\n        int[] parent = new int[n];\n        for(int i=0;i<n;i++){\n            adj.add(new HashSet<>()); // We use hashset so that removal of edge is quick\n            parent[i] = -1;\n        }\n        for(List<Integer> edge: connections) {\n            adj.get(edge.get(0)).add(edge.get(1));\n            adj.get(edge.get(1)).add(edge.get(0));\n        }\n        \n        Stack<Integer> stack = new Stack<>();\n        boolean[] visited = new boolean[n];\n        for(int i=0;i<n;i++) {\n            if(!visited[i]){\n                getOrder(adj, stack, parent, visited, i); // Fill stack for ordering\n            }\n        }\n        \n        for(int i=0;i<n;i++){\n            if(parent[i]!=-1){\n                adj.get(parent[i]).remove(i); // This is similar to the case where we have to build the transpose graph as per Kosaraju\'s Algo\n            }\n        }\n        Arrays.fill(visited, false);\n        \n        List<List<Integer>> criticals = new ArrayList<>();\n        while(!stack.isEmpty()) {\n            int v = stack.pop();\n            if(!visited[v]){\n                if(parent[v]!=-1){\n                    criticals.add(Arrays.asList(parent[v], v)); // Whenever we pop from stack and the component is unvisited it means a new SCC \n                }\n                dfs(adj, visited, v);\n            }\n        }\n        \n        return criticals;\n    }\n    \n    private void getOrder(List<Set<Integer>> adj, Stack<Integer> stack, int[] parent, boolean[] visited, int s) {\n        visited[s] = true;\n        \n        for(int n: adj.get(s)) {\n            if(!visited[n]){\n                parent[n] = s;\n                getOrder(adj, stack, parent, visited, n);\n            }\n        }\n        \n        stack.push(s);\n    }\n    \n    private void dfs(List<Set<Integer>> adj, boolean[] visited, int s) {\n        visited[s] = true;\n        \n        for(int n: adj.get(s)) {\n            if(!visited[n]){\n                dfs(adj, visited, n);\n            }\n        }\n        \n    }\n}\n```\n\n**Tarjan\'s Algorithm** `Complexity: O(V+E)`\n*One DFS Traversal*\n* This algorithm uses the concept of the discovery & low time to find the back-edge\n* If for any edge `u->v` , `low[v] > disc[u]` it means that the lowest node which can be reached from `v` comes after `u` therefore there is no way to reach the strongly connected component which contains the node `u`. Therefore `u->v` is a critical connection\n\n```\nclass Solution {\n    private int time = 0;\n    \n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        List<List<Integer>> adj = new ArrayList<>();\n        int[] parent = new int[n];\n        int[] disc = new int[n];\n        int[] low = new int[n];\n        \n        for(int i=0;i<n;i++){\n            adj.add(new ArrayList<>());\n            parent[i] = -1;\n            disc[i] = -1;\n            low[i] = -1;\n        }\n        \n        for(List<Integer> edge: connections) {\n            adj.get(edge.get(0)).add(edge.get(1));\n            adj.get(edge.get(1)).add(edge.get(0));\n        }\n        \n        List<List<Integer>> criticals = new ArrayList<>();\n        dfs(adj, criticals, disc, low, parent, 0);\n        \n        return criticals;\n    }\n    \n    private void dfs(List<List<Integer>> adj, List<List<Integer>> criticals, int[] disc, int[] low, int[] parent, int u) {\n        disc[u] = time;\n        low[u] = time;\n        time++;\n        \n        for(int v: adj.get(u)){\n            if(disc[v]==-1) {\n                parent[v] = u;\n                dfs(adj,criticals, disc,low,parent,v);\n                low[u] = Math.min(low[u], low[v]);\n                \n                if(low[v]>disc[u]){\n                    criticals.add(Arrays.asList(u,v));\n                }\n            } else if(parent[u]!=v) {\n                low[u] = Math.min(low[u], disc[v]);\n            }\n        }\n    }\n}\n```\n\nPlease upvote if you felt this is easy to understand and explains both the linear algorithms so that it can help others.
['Depth-First Search', 'Graph', 'Java']