{"id":"55b73bd6-6e8e-48bc-b501-94d2af8e87f1","name":"Kosaraju Algorithm","description":"You are given a graph with N nodes and M directed edges. Find the number of Strongly connected components in the graph.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.","outputFormat":"Print in one line the number of strongly connected components in the graph.","constraints":"1<= N <= 10000\r\n1<= M <= (N*(N-1))/2\r\n1<= ai, bi <= N","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint kosaraju(vector<vector<int>> & graph,int N){\n \n}\n\nint main(){\n int n, m;\n cin>>n>>m;\n vector<vector<int>>graph(n); \n\tfor(int i = 0;i<m;i++) {\n\t int u, v;\n\t cin >> u >> v; \n\t graph[u-1].push_back(v-1);\n\t}\n cout<<kosaraju(graph, n);\n}\n"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n\tpublic static void main(String args[]) throws Exception {\n\t BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\t\tString[] st = br.readLine().split(\" \");\n\t\tint n = Integer.parseInt(st[0]);\n\t\tint m = Integer.parseInt(st[1]);\n\n\t\tArrayList<ArrayList<Integer>> graph = new ArrayList<>();\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tgraph.add(new ArrayList<>());\n\t\t}\n\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tst = br.readLine().split(\" \");\n\t\t\tint u = Integer.parseInt(st[0]) - 1;\n\t\t\tint v = Integer.parseInt(st[1]) - 1;\n\t\t\tgraph.get(u).add(v);\n\t\t}\n\n\t\tSystem.out.println(kosaraju(graph, n));\n\t}\n\n\tpublic static int kosaraju(ArrayList<ArrayList<Integer>> list, int N) {\n\t\t\n }\t\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"5 6\r\n1 4\r\n1 3\r\n2 4\r\n3 4\r\n4 5\r\n5 1","sampleOutput":"2\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":"03a49e10-d089-4b59-b2a4-0e895f108f52","name":"Kosaraju Algorithm","slug":"kosaraju-algorithm","type":1}],"next":{"id":"6d34e581-d33d-43f0-80ca-d120d534c463","name":"Kosaraju Algorithm MCQ","type":0,"slug":"kosaraju-algorithm-mcq"},"prev":{"id":"f96b2fff-d3b2-4efd-b16d-eb0a8d62014e","name":"Redundant Connection","type":3,"slug":"redundant-connection"}}}You are given a graph with N nodes and M directed edges. Find the number of Strongly connected components in the graph.
{"id":"55b73bd6-6e8e-48bc-b501-94d2af8e87f1","name":"Kosaraju Algorithm","description":"You are given a graph with N nodes and M directed edges. Find the number of Strongly connected components in the graph.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.","outputFormat":"Print in one line the number of strongly connected components in the graph.","constraints":"1<= N <= 10000\r\n1<= M <= (N*(N-1))/2\r\n1<= ai, bi <= N","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint kosaraju(vector<vector<int>> & graph,int N){\n \n}\n\nint main(){\n int n, m;\n cin>>n>>m;\n vector<vector<int>>graph(n); \n\tfor(int i = 0;i<m;i++) {\n\t int u, v;\n\t cin >> u >> v; \n\t graph[u-1].push_back(v-1);\n\t}\n cout<<kosaraju(graph, n);\n}\n"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n\tpublic static void main(String args[]) throws Exception {\n\t BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\t\tString[] st = br.readLine().split(\" \");\n\t\tint n = Integer.parseInt(st[0]);\n\t\tint m = Integer.parseInt(st[1]);\n\n\t\tArrayList<ArrayList<Integer>> graph = new ArrayList<>();\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tgraph.add(new ArrayList<>());\n\t\t}\n\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tst = br.readLine().split(\" \");\n\t\t\tint u = Integer.parseInt(st[0]) - 1;\n\t\t\tint v = Integer.parseInt(st[1]) - 1;\n\t\t\tgraph.get(u).add(v);\n\t\t}\n\n\t\tSystem.out.println(kosaraju(graph, n));\n\t}\n\n\tpublic static int kosaraju(ArrayList<ArrayList<Integer>> list, int N) {\n\t\t\n }\t\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"5 6\r\n1 4\r\n1 3\r\n2 4\r\n3 4\r\n4 5\r\n5 1","sampleOutput":"2\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":"03a49e10-d089-4b59-b2a4-0e895f108f52","name":"Kosaraju Algorithm","slug":"kosaraju-algorithm","type":1}],"next":{"id":"6d34e581-d33d-43f0-80ca-d120d534c463","name":"Kosaraju Algorithm MCQ","type":0,"slug":"kosaraju-algorithm-mcq"},"prev":{"id":"f96b2fff-d3b2-4efd-b16d-eb0a8d62014e","name":"Redundant Connection","type":3,"slug":"redundant-connection"}}}
Editor
Discussions
Show Discussion
Related Resources
