Striver's Solution with proper explanation and visualization! (Video)
Vide Link\nhttps://www.youtube.com/watch?v=qrAub5z8FeA\n# Approach\nLet\'s understand the solution with the help of an example:-\n\n\nWe need to find links that
# Vide Link\nhttps://www.youtube.com/watch?v=qrAub5z8FeA\n# Approach\nLet\'s understand the solution with the help of an example:-\n![image.png](https://assets.leetcode.com/users/images/cb1e7c9c-d529-4754-945b-2703cb45b779_1694683071.9864287.png)\n\nWe need to find links that if destroyed would seperate our graph into `2 or more components`.\n\nTo solve this we first convert the `connections` given into a `adjacency matrix`, which will tell us the adjacent nodes for every node in the graph.\n\nWe\'ll need a` visited array vis `to check if certain node is already visited or not. `0- not visited, 1- visited.`\n \nWe also have 2 arrays` low `and` tin` , low stores the lowest time of insertion and tin stores the time of insertion.\n\n`lowest time of insertion tells us the lowest time of insertion of adjacent nodes of a node.\nWhereas tin tells us the time of insertion of current node.`\n\nWe have a `timer` for this.\n\nCreate a result array` bridges` to store our result.\nWe then call our `dfs` function whose working is explained below-\n\n- At first we mark our current node as visited, then `tin[node] = low[node] = timer`, `increment the timer` and then we look into adjacent nodes of our current node.\n- for every adjacent node if we it is not visited, we perform `dfs on that node`, after dfs we relax it by` updating its low[node] `value.\n- If the the adjacent node\'s low value is more than current node\'s tin, it means that we\'ve found a bridge and hence we push both into our bridges array. This is because the low value tells us the lowest node from which we can come to the node and if its value is more than\ntimer for current node, we can\'t reach the node.\n- If the adjacent node was already visited, we just update the node\'s low value.\n\n# Explanation of the question\nIn the below graph you can see I\'ve marked the `low values in green and tin values in blue`.\n\n![image.png](https://assets.leetcode.com/users/images/b71c0d66-f86f-4a61-9ccd-bfdc657d3ff9_1694683827.0461073.png)\n\nAs you can see in the code the `dfs` function is called `recursively`, until we reach `12` whose all adjacents are already visited.\n\n![image.png](https://assets.leetcode.com/users/images/994c523c-0406-4f97-b3cf-b94014f54314_1694683860.5348027.png)\n\nAfter 12, we return to its parent 11, relax its values and then to 10 and we continue this till we\'re in the `first recursion call.`\n\n![image.png](https://assets.leetcode.com/users/images/26fdd0fc-ea39-4ac6-915d-e3c60edb254f_1694683926.5528395.png)\n\nIn the meantime, we also check for `if (low[it] > tin[node])`, if so we `push node and adjacent` into our result.\n\n![image.png](https://assets.leetcode.com/users/images/9cb63932-71cc-4c48-9ae3-c64830333e06_1694683959.5322042.png)\n\n\n\n\n\n# Code\n```\nclass Solution {\nprivate:\n    int timer = 1;\n    void dfs(int node, int parent, vector<int> &vis,\n             vector<int> adj[], int tin[], int low[], vector<vector<int>> &bridges) {\n        vis[node] = 1;\n        tin[node] = low[node] = timer;\n        timer++;\n        for (auto it : adj[node]) {\n            if (it == parent) continue;\n            if (vis[it] == 0) {\n                dfs(it, node, vis, adj, tin, low, bridges);\n                low[node] = min(low[it], low[node]);\n                // node --- it\n                if (low[it] > tin[node]) {\n                    bridges.push_back({it, node});\n                }\n            }\n            else {\n                low[node] = min(low[node], low[it]);\n            }\n        }\n    }\npublic:\n    vector<vector<int>> criticalConnections(int n,\n    vector<vector<int>>& connections) {\n        vector<int> adj[n];\n        for (auto it : connections) {\n            int u = it[0], v = it[1];\n            adj[u].push_back(v);\n            adj[v].push_back(u);\n        }\n        vector<int> vis(n, 0);\n        int tin[n];\n        int low[n];\n        vector<vector<int>> bridges;\n        dfs(0, -1, vis, adj, tin, low, bridges);\n        return bridges;\n    }\n};\n```
['Greedy', 'Depth-First Search', 'C++', 'Java']