{"id":"bdf2adad-da82-4f04-a726-01a09372ae0d","name":"Critical Connection","description":"An edge in an undirected graph is a Bridge iff removing it disconnects the graph. You have to print all the Bridges of the given graph.","inputFormat":"First line contains two integers V and E.\r\nEach of next E line contains two integer u and v denoting an edge between vertex u and v.","outputFormat":"Print all the bridges.","constraints":"1 &lt;= number of vertices(V) &lt;= 1000\r\n1 &lt;= number of Edges(E) &lt;= V*(V-1)/2;","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>parent;\nvector<int>disc;\nvector<int>low;\nvector<bool>vis;\n\nint timer;\n\nvoid bridges(int u,vector<vector<int>>& graph,vector<vector<int>>& ans){\n //write your code here\n}\n\n\nvector<vector<int>> criticalConnection(int n,vector<vector<int>>& edges){\n vector<vector<int>>graph(n);\n \n for(int i=0;i<edges.size();i++){\n int u=edges[i][0];\n int v=edges[i][1];\n \n graph[u].push_back(v);\n graph[v].push_back(u);\n }\n \n parent.resize(n);\n disc.resize(n);\n low.resize(n);\n vis.resize(n);\n \n timer=0;\n \n vector<vector<int>>ans;\n bridges(0,graph,ans);\n \n return ans;\n}\n\n\nint main(){\n \n int n,e;\n cin>>n>>e;\n \n vector<vector<int>>edges(e);\n \n for(int i=0;i<e;i++){\n int x,y;\n cin>>x>>y;\n edges[i].push_back(x);\n edges[i].push_back(y);\n \n }\n \n vector<vector<int>>ans=criticalConnection(n,edges);\n \n \n cout<<'[';\n for(int i=0;i<ans.size();i++){\n cout<<'[';\n for(int j=0;j<ans[0].size();j++){\n if(j==ans[0].size()-1){\n cout<<ans[i][j];\n }else{\n cout<<ans[i][j]<<\", \";\n }\n }\n if(i==ans.size()-1){\n cout<<\"]\";\n }else{\n cout<<\"], \";\n }\n }\n cout<<\"]\";\n \n \n}"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\nclass Main {\r\n\r\n public static List<List<Integer>> criticalConnections(int n, List<List<Integer>> Edges) {\r\n\r\n\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int n = Integer.parseInt(st[0]);\r\n int e = Integer.parseInt(st[1]);\r\n List<List<Integer>> edges = new ArrayList<>();\r\n\r\n\r\n for (int i = 0; i < e; i++) {\r\n edges.add(new ArrayList<>());\r\n st = br.readLine().split(\" \");\r\n edges.get(i).add(Integer.parseInt(st[0]));\r\n edges.get(i).add(Integer.parseInt(st[1]));\r\n }\r\n\r\n System.out.println(criticalConnections(n, edges));\r\n\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"5 5\r\n0 1\r\n0 2\r\n2 1\r\n2 3\r\n4 3","sampleOutput":"[[3, 4], [2, 3]]\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"5fe380f2-5d77-4e78-b17d-0345569e9bbb","name":"Critical Connection","slug":"critical-connection","type":1}],"next":{"id":"644d7465-ed13-42e1-8163-aa872f59a0f0","name":"Critical Connection Medium MCQ","type":0,"slug":"critical-connection-medium-mcq"},"prev":{"id":"5b1252c0-8d7b-481c-a45e-3a01babd3185","name":"Eulerian Path and Circuit","type":3,"slug":"eulerian-path-and-circuit"}}}

Critical Connection

An edge in an undirected graph is a Bridge iff removing it disconnects the graph. You have to print all the Bridges of the given graph.

{"id":"bdf2adad-da82-4f04-a726-01a09372ae0d","name":"Critical Connection","description":"An edge in an undirected graph is a Bridge iff removing it disconnects the graph. You have to print all the Bridges of the given graph.","inputFormat":"First line contains two integers V and E.\r\nEach of next E line contains two integer u and v denoting an edge between vertex u and v.","outputFormat":"Print all the bridges.","constraints":"1 &lt;= number of vertices(V) &lt;= 1000\r\n1 &lt;= number of Edges(E) &lt;= V*(V-1)/2;","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>parent;\nvector<int>disc;\nvector<int>low;\nvector<bool>vis;\n\nint timer;\n\nvoid bridges(int u,vector<vector<int>>& graph,vector<vector<int>>& ans){\n //write your code here\n}\n\n\nvector<vector<int>> criticalConnection(int n,vector<vector<int>>& edges){\n vector<vector<int>>graph(n);\n \n for(int i=0;i<edges.size();i++){\n int u=edges[i][0];\n int v=edges[i][1];\n \n graph[u].push_back(v);\n graph[v].push_back(u);\n }\n \n parent.resize(n);\n disc.resize(n);\n low.resize(n);\n vis.resize(n);\n \n timer=0;\n \n vector<vector<int>>ans;\n bridges(0,graph,ans);\n \n return ans;\n}\n\n\nint main(){\n \n int n,e;\n cin>>n>>e;\n \n vector<vector<int>>edges(e);\n \n for(int i=0;i<e;i++){\n int x,y;\n cin>>x>>y;\n edges[i].push_back(x);\n edges[i].push_back(y);\n \n }\n \n vector<vector<int>>ans=criticalConnection(n,edges);\n \n \n cout<<'[';\n for(int i=0;i<ans.size();i++){\n cout<<'[';\n for(int j=0;j<ans[0].size();j++){\n if(j==ans[0].size()-1){\n cout<<ans[i][j];\n }else{\n cout<<ans[i][j]<<\", \";\n }\n }\n if(i==ans.size()-1){\n cout<<\"]\";\n }else{\n cout<<\"], \";\n }\n }\n cout<<\"]\";\n \n \n}"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\nclass Main {\r\n\r\n public static List<List<Integer>> criticalConnections(int n, List<List<Integer>> Edges) {\r\n\r\n\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int n = Integer.parseInt(st[0]);\r\n int e = Integer.parseInt(st[1]);\r\n List<List<Integer>> edges = new ArrayList<>();\r\n\r\n\r\n for (int i = 0; i < e; i++) {\r\n edges.add(new ArrayList<>());\r\n st = br.readLine().split(\" \");\r\n edges.get(i).add(Integer.parseInt(st[0]));\r\n edges.get(i).add(Integer.parseInt(st[1]));\r\n }\r\n\r\n System.out.println(criticalConnections(n, edges));\r\n\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"5 5\r\n0 1\r\n0 2\r\n2 1\r\n2 3\r\n4 3","sampleOutput":"[[3, 4], [2, 3]]\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"5fe380f2-5d77-4e78-b17d-0345569e9bbb","name":"Critical Connection","slug":"critical-connection","type":1}],"next":{"id":"644d7465-ed13-42e1-8163-aa872f59a0f0","name":"Critical Connection Medium MCQ","type":0,"slug":"critical-connection-medium-mcq"},"prev":{"id":"5b1252c0-8d7b-481c-a45e-3a01babd3185","name":"Eulerian Path and Circuit","type":3,"slug":"eulerian-path-and-circuit"}}}
plane

Editor


Loading...

Critical Connection

easy

An edge in an undirected graph is a Bridge iff removing it disconnects the graph. You have to print all the Bridges of the given graph.

Constraints

1 <= number of vertices(V) <= 1000 1 <= number of Edges(E) <= V*(V-1)/2;

Format

Input

First line contains two integers V and E. Each of next E line contains two integer u and v denoting an edge between vertex u and v.

Output

Print all the bridges.

Example

Sample Input

5 5 0 1 0 2 2 1 2 3 4 3

Sample Output

[[3, 4], [2, 3]]

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode