{"id":"95bd598b-689c-4635-8f39-de422ea9c1a5","name":"Hamiltonian Path And Cycle","description":"1. You are given a graph and a src vertex.\r\n2. You are required to find and print all hamiltonian paths and cycles starting from src. The cycles must end with \"*\" and paths with a \".\"\r\n\r\nNote -> A hamiltonian path is such which visits all vertices without visiting any twice. A hamiltonian path becomes a cycle if there is an edge between first and last vertex.\r\nNote -> Print in lexicographically increasing order.","inputFormat":"Input has been managed for you","outputFormat":"Check sample output","constraints":"None","sampleCode":{"cpp":{"code":""},"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 int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\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 int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n\r\n // write all your codes here\r\n }\r\n\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7\r\n9\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n2 5 10\r\n0","sampleOutput":"0123456.\r\n0123465.\r\n0125643*\r\n0346521*","questionVideo":"https://www.youtube.com/embed/nUgp0RG57wQ?end=152\r\n","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":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"2c6531b8-7b77-4e5f-b927-086c0c78ec82","name":"Hamiltonian Path And Cycle","slug":"hamiltonian-path-and-cycle","type":1}],"next":{"id":"d33b0418-358c-4a2b-94a3-08189f022b40","name":"Hamiltonian Path and Cycle","type":3,"slug":"hamiltonian-path-and-cycle"},"prev":{"id":"c85f9941-f0d3-45db-9158-4e9052bbc859","name":"Perfect Friends","type":3,"slug":"perfect-friends"}}}

Hamiltonian Path And Cycle

1. You are given a graph and a src vertex. 2. You are required to find and print all hamiltonian paths and cycles starting from src. The cycles must end with "*" and paths with a "." Note -> A hamiltonian path is such which visits all vertices without visiting any twice. A hamiltonian path becomes a cycle if there is an edge between first and last vertex. Note -> Print in lexicographically increasing order.

{"id":"95bd598b-689c-4635-8f39-de422ea9c1a5","name":"Hamiltonian Path And Cycle","description":"1. You are given a graph and a src vertex.\r\n2. You are required to find and print all hamiltonian paths and cycles starting from src. The cycles must end with \"*\" and paths with a \".\"\r\n\r\nNote -> A hamiltonian path is such which visits all vertices without visiting any twice. A hamiltonian path becomes a cycle if there is an edge between first and last vertex.\r\nNote -> Print in lexicographically increasing order.","inputFormat":"Input has been managed for you","outputFormat":"Check sample output","constraints":"None","sampleCode":{"cpp":{"code":""},"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 int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\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 int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n\r\n // write all your codes here\r\n }\r\n\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7\r\n9\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n2 5 10\r\n0","sampleOutput":"0123456.\r\n0123465.\r\n0125643*\r\n0346521*","questionVideo":"https://www.youtube.com/embed/nUgp0RG57wQ?end=152\r\n","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":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"2c6531b8-7b77-4e5f-b927-086c0c78ec82","name":"Hamiltonian Path And Cycle","slug":"hamiltonian-path-and-cycle","type":1}],"next":{"id":"d33b0418-358c-4a2b-94a3-08189f022b40","name":"Hamiltonian Path and Cycle","type":3,"slug":"hamiltonian-path-and-cycle"},"prev":{"id":"c85f9941-f0d3-45db-9158-4e9052bbc859","name":"Perfect Friends","type":3,"slug":"perfect-friends"}}}
plane

Editor

Loading...

Hamiltonian Path And Cycle

easy

1. You are given a graph and a src vertex. 2. You are required to find and print all hamiltonian paths and cycles starting from src. The cycles must end with "*" and paths with a "." Note -> A hamiltonian path is such which visits all vertices without visiting any twice. A hamiltonian path becomes a cycle if there is an edge between first and last vertex. Note -> Print in lexicographically increasing order.

Constraints

None

Format

Input

Input has been managed for you

Output

Check sample output

Example

Sample Input

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

Sample Output

0123456. 0123465. 0125643* 0346521*

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode