package com.thealgorithms.datastructures.graphs;
import java.util.ArrayList;
import java.util.Scanner;
class Cycle {
private final int nodes;
private final int edges;
private int[][] adjacencyMatrix;
private boolean[] visited;
ArrayList<ArrayList<Integer>> cycles = new ArrayList<ArrayList<Integer>>();
Cycle() {
Scanner in = new Scanner(System.in);
System.out.print("Enter the no. of nodes: ");
nodes = in.nextInt();
System.out.print("Enter the no. of Edges: ");
edges = in.nextInt();
adjacencyMatrix = new int[nodes][nodes];
visited = new boolean[nodes];
for (int i = 0; i < nodes; i++) {
visited[i] = false;
}
System.out.println("Enter the details of each edges <Start Node> <End Node>");
for (int i = 0; i < edges; i++) {
int start;
int end;
start = in.nextInt();
end = in.nextInt();
adjacencyMatrix[start][end] = 1;
}
in.close();
}
public void start() {
for (int i = 0; i < nodes; i++) {
ArrayList<Integer> temp = new ArrayList<>();
dfs(i, i, temp);
for (int j = 0; j < nodes; j++) {
adjacencyMatrix[i][j] = 0;
adjacencyMatrix[j][i] = 0;
}
}
}
private void dfs(Integer start, Integer curr, ArrayList<Integer> temp) {
temp.add(curr);
visited[curr] = true;
for (int i = 0; i < nodes; i++) {
if (adjacencyMatrix[curr][i] == 1) {
if (i == start) {
cycles.add(new ArrayList<Integer>(temp));
} else {
if (!visited[i]) {
dfs(start, i, temp);
}
}
}
}
if (temp.size() > 0) {
temp.remove(temp.size() - 1);
}
visited[curr] = false;
}
public void printAll() {
for (int i = 0; i < cycles.size(); i++) {
for (int j = 0; j < cycles.get(i).size(); j++) {
System.out.print(cycles.get(i).get(j) + " -> ");
}
System.out.println(cycles.get(i).get(0));
System.out.println();
}
}
}
public final class Cycles {
private Cycles() {
}
public static void main(String[] args) {
Cycle c = new Cycle();
c.start();
c.printAll();
}
}