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:

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