Problem Statement:
Given an undirected Graph, write an algorithm that returns True if the graph contains a cycle, otherwise False.
Example 1:
Input: vertices=7, edges=[[0, 1], [0, 4], [0, 5], [1, 2], [2, 3], [5, 6]] Output: false
Example 2:
Input: vertices=7, edges=[[0, 1], [0, 4], [0, 5], [1, 2], [2, 3], [4, 5], [5, 6]] Output: true
Code:
Java
C++
Python
import java.util.*; class Innoskrit { // building graph public HashMap<Integer, ArrayList<Integer>> buildGraph(int vertices, int edges[][]) { HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>(); for(int i = 0; i < vertices; i++) { graph.put(i, new ArrayList<>()); } for(int i = 0; i < edges.length; i++) { int parent = edges[i][0]; int child = edges[i][1]; graph.get(parent).add(child); graph.get(child).add(parent); } return graph; } public boolean containsCycle(int vertices, int edges[][]) { HashMap<Integer, ArrayList<Integer>> graph = buildGraph(vertices, edges); boolean visited[] = new boolean[vertices]; for(int node = 0; node < vertices; node++) { if(!visited[node]) { if(dfs(node, -1, visited, graph)) { return true; } } } return false; } public boolean dfs(int node, int parent, boolean visited[], HashMap<Integer, ArrayList<Integer>> graph) { visited[node] = true; for(int nbr : graph.get(node)) { if(!visited[nbr]) { if(dfs(nbr, node, visited, graph)) return true; } else if(nbr != parent) { return true; } } return false; } public static void main(String[] args) { Innoskrit obj = new Innoskrit(); int vertices = 7; int edges[][] = new int[][] {{0, 1}, {0, 4}, {0, 5}, {1, 2}, {2, 3}, {4, 5}, {5, 6}}; System.out.println(obj.containsCycle(vertices, edges)); } }
Output:
true