staticclassGraph{ int vertices; LinkedList<Integer>[] adjList;
publicGraph(int vertices){ this.vertices = vertices; adjList = new LinkedList[vertices]; for (int i = 0; i < vertices; i++) { adjList[i] = new LinkedList<>(); } }
publicbooleanisCycle(){ // visited array boolean[] visited = newboolean[vertices]; // do DFS, from each vertex for (int i = 0; i < vertices; i++) { if (!visited[i]) { if (isCycleUtil(i, visited, -1)) { returntrue; } } } returnfalse; }
booleanisCycleUtil(int currVertex, boolean[] visited, int parent){ // add this vertex to visited vertex visited[currVertex] = true;
for (int i = 0; i < adjList[currVertex].size(); i++) { int vertex = adjList[currVertex].get(i); // If an adjacent is not visited, then recur for that // adjacent if (!visited[vertex]) { if (isCycleUtil(vertex, visited, currVertex)) { returntrue; } } // If an adjacent is visited and not parent of current // vertex, then there is a cycle. elseif (vertex != parent) { returntrue; } } returnfalse; } } }