PR2.java

importjava.util.*;

publicclassPR2 {

publicstaticbooleandetectCycle(int[][] edgeList) {
if (edgeList.length == 0) {
returnfalse;
 }

Map<Integer, Set<Integer>> graph = newHashMap<>();
int[] inorder = newint[edgeList.length];

for (int[] edge : edgeList) {
graph.putIfAbsent(edge[0], newHashSet<>());
graph.get(edge[0]).add(edge[1]);

inorder[edge[1]]++;
 }

Queue<Integer> q = newLinkedList<>();

for (inti = 0; i < inorder.length; i++) {
if (inorder[i] == 0) {
q.offer(i);
 }
 }

intnodeCount = 0;

while (!q.isEmpty()) {
intkey = q.poll();
 ++nodeCount;

if (!graph.containsKey(key)) {
continue;
 }

for (intneighbour : graph.get(key)) {
inorder[neighbour]--;

if (inorder[neighbour] == 0) {
q.offer(neighbour);
 }
 }
 }

returnedgeList.length - nodeCount > 1;
 }

publicstaticvoidmain(String[] args) {
int[][] edgeList1 = newint[][] { { 0, 1 }, { 1, 3 }, { 2, 3 }, { 1, 2 }, { 4, 1 }, { 0, 4 }, { 1, 3 } };
int[][] edgeList2 = newint[][] { { 0, 1 }, { 1, 3 }, { 2, 3 }, { 3, 4 }, { 1, 2 }, { 4, 1 }, { 0, 4 } };

System.out.println(detectCycle(edgeList1)); // no cycle - return false
System.out.println(detectCycle(edgeList2)); // cycle present - return true

return;
 }
}