{"id":"eff59b07-1719-419e-a05b-81d459ce423b","name":"Order Of Compilation","description":"1. You are given a directed acyclic graph. The vertices represent tasks and edges represent \r\n dependencies between tasks.\r\n2. You are required to find and print the order in which tasks could be done. The task that should be \r\n done at last should be printed first and the task which should be done first should be printed last. \r\n This is called topological sort. Check out the question video for details.\r\n\r\nTopological sort -> A permutation of vertices for a directed acyclic graph is called topological sort if \r\n for all directed edges uv, u appears before v in the graph\r\n\r\nNote -> For output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n\nusing namespace std;\n\nclass Edge\n{ \npublic:\n int src = 0; \n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n\n }\n};\n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n \n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) { \n int u, v; \n cin >> u >> v; \n \n graph[u].push_back(Edge(u, v)); \n } \n\n //write your code here \n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n\r\n Edge(int src, int nbr) {\r\n this.src = src;\r\n this.nbr = nbr;\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\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n graph[v1].add(new Edge(v1, v2));\r\n }\r\n\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import threading , queue\n\nclass Edge:\n def __init__(self,src,nbr):\n self.src = src\n self.nbr = nbr\n \n\ndef main():\n vtces = int(input())\n edges = int(input()) \n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges): \n lines = input().split(\" \") \n v1=int(lines[0]) \n v2=int(lines[1])\n e1 = Edge(v1 ,v2 ) \n graph[e1.src].append(e1) \n \n # Write your code here \n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n7\r\n0 1\r\n1 2\r\n2 3\r\n0 3\r\n4 5\r\n5 6\r\n4 6","sampleOutput":"4\r\n5\r\n6\r\n0\r\n1\r\n2\r\n3","questionVideo":"https://www.youtube.com/embed/6Vi5Td_a8B8","hints":[],"associated":[{"id":"235e01da-95db-4863-899a-eb8812b448ac","name":"If N and E represent number of vertices and number of edges respectively, what will be the time complexity of \"Order of Compilation\" problem?","slug":"if-n-and-e-represent-number-of-vertices-and-number-of-edges-respectively-what-will-be-the-time-complexity-of-order-of-compilation-problem","type":4},{"id":"8c1c0279-1f61-45ea-a86c-cc9d2ec5e505","name":"What kind of sorting is used in this \"Order of Compilation\" problem?","slug":"what-kind-of-sorting-is-used-in-this-order-of-compilation-problem","type":4},{"id":"8cb3b772-8ed2-4db4-99ad-9414e384a1b5","name":"What is the data structure used in \"Order of Compilation\" problem?","slug":"what-is-the-data-structure-used-in-order-of-compilation-problem","type":4},{"id":"cdc3965d-7302-4844-9095-6a08f62220da","name":"Topological Sort can only be done in: (Order of Compilation)","slug":"topological-sort-can-only-be-done-in-order-of-compilation","type":4}],"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":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"de78cfc6-f4ff-4dcc-8f4e-f2ba73e6907c","name":"Order Of Compilation","slug":"order-of-compilation","type":1}],"next":{"id":"88cb03ca-e99a-4714-a359-8d65cbb9eb88","name":"Order of Compilation","type":3,"slug":"order-of-compilation"},"prev":{"id":"fbeaf6b1-afec-46d8-9410-38ad6bc5b0c1","name":"MIN WIRE REQUIRED TO CONNECT ALL PCS","type":3,"slug":"min-wire-required-to-connect-all-pcs"}}}

Order Of Compilation

1. You are given a directed acyclic graph. The vertices represent tasks and edges represent dependencies between tasks. 2. You are required to find and print the order in which tasks could be done. The task that should be done at last should be printed first and the task which should be done first should be printed last. This is called topological sort. Check out the question video for details. Topological sort -> A permutation of vertices for a directed acyclic graph is called topological sort if for all directed edges uv, u appears before v in the graph Note -> For output, check the sample output and question video.

{"id":"eff59b07-1719-419e-a05b-81d459ce423b","name":"Order Of Compilation","description":"1. You are given a directed acyclic graph. The vertices represent tasks and edges represent \r\n dependencies between tasks.\r\n2. You are required to find and print the order in which tasks could be done. The task that should be \r\n done at last should be printed first and the task which should be done first should be printed last. \r\n This is called topological sort. Check out the question video for details.\r\n\r\nTopological sort -> A permutation of vertices for a directed acyclic graph is called topological sort if \r\n for all directed edges uv, u appears before v in the graph\r\n\r\nNote -> For output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n\nusing namespace std;\n\nclass Edge\n{ \npublic:\n int src = 0; \n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n\n }\n};\n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n \n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) { \n int u, v; \n cin >> u >> v; \n \n graph[u].push_back(Edge(u, v)); \n } \n\n //write your code here \n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n\r\n Edge(int src, int nbr) {\r\n this.src = src;\r\n this.nbr = nbr;\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\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n graph[v1].add(new Edge(v1, v2));\r\n }\r\n\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import threading , queue\n\nclass Edge:\n def __init__(self,src,nbr):\n self.src = src\n self.nbr = nbr\n \n\ndef main():\n vtces = int(input())\n edges = int(input()) \n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges): \n lines = input().split(\" \") \n v1=int(lines[0]) \n v2=int(lines[1])\n e1 = Edge(v1 ,v2 ) \n graph[e1.src].append(e1) \n \n # Write your code here \n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n7\r\n0 1\r\n1 2\r\n2 3\r\n0 3\r\n4 5\r\n5 6\r\n4 6","sampleOutput":"4\r\n5\r\n6\r\n0\r\n1\r\n2\r\n3","questionVideo":"https://www.youtube.com/embed/6Vi5Td_a8B8","hints":[],"associated":[{"id":"235e01da-95db-4863-899a-eb8812b448ac","name":"If N and E represent number of vertices and number of edges respectively, what will be the time complexity of \"Order of Compilation\" problem?","slug":"if-n-and-e-represent-number-of-vertices-and-number-of-edges-respectively-what-will-be-the-time-complexity-of-order-of-compilation-problem","type":4},{"id":"8c1c0279-1f61-45ea-a86c-cc9d2ec5e505","name":"What kind of sorting is used in this \"Order of Compilation\" problem?","slug":"what-kind-of-sorting-is-used-in-this-order-of-compilation-problem","type":4},{"id":"8cb3b772-8ed2-4db4-99ad-9414e384a1b5","name":"What is the data structure used in \"Order of Compilation\" problem?","slug":"what-is-the-data-structure-used-in-order-of-compilation-problem","type":4},{"id":"cdc3965d-7302-4844-9095-6a08f62220da","name":"Topological Sort can only be done in: (Order of Compilation)","slug":"topological-sort-can-only-be-done-in-order-of-compilation","type":4}],"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":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"de78cfc6-f4ff-4dcc-8f4e-f2ba73e6907c","name":"Order Of Compilation","slug":"order-of-compilation","type":1}],"next":{"id":"88cb03ca-e99a-4714-a359-8d65cbb9eb88","name":"Order of Compilation","type":3,"slug":"order-of-compilation"},"prev":{"id":"fbeaf6b1-afec-46d8-9410-38ad6bc5b0c1","name":"MIN WIRE REQUIRED TO CONNECT ALL PCS","type":3,"slug":"min-wire-required-to-connect-all-pcs"}}}
plane

Editor

Loading...

Order Of Compilation

easy

1. You are given a directed acyclic graph. The vertices represent tasks and edges represent dependencies between tasks. 2. You are required to find and print the order in which tasks could be done. The task that should be done at last should be printed first and the task which should be done first should be printed last. This is called topological sort. Check out the question video for details. Topological sort -> A permutation of vertices for a directed acyclic graph is called topological sort if for all directed edges uv, u appears before v in the graph Note -> For output, check the sample output and question video.

Constraints

None

Format

Input

Input has been managed for you

Output

Check the sample output

Example

Sample Input

7 7 0 1 1 2 2 3 0 3 4 5 5 6 4 6

Sample Output

4 5 6 0 1 2 3

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode