find if it is possible to complete a given task

 import java.util.*;


public class PossibleToFinishATask {
    public static ArrayList<Integer>[] Create(int n, int prerequisites[][]) {
        ArrayList<Integer> graph[] = new ArrayList[n];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int arr[] : prerequisites) {
            int u = arr[0];
            int v = arr[1];
            graph[u].add(v);
        }
        return graph;
    }

    public static boolean isCycle(ArrayList<Integer> graph[], int n) {
        int indegree[] = new int[n];

        for (int i = 0; i < n; i++) {
            for (int neighbour : graph[i]) {
                indegree[neighbour]++;
            }
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.add(i);
            }
        }
        int count = 0;
        while (!q.isEmpty()) {
            int curr = q.remove();
            count++;
            for (int neighbour : graph[curr]) {
                indegree[neighbour]--;
                if (indegree[neighbour] == 0) {
                    q.add(neighbour);
                }
            }
        }
        return count != n;
    }

    public static boolean Possible(int n, int prerequisites[][]) {
        if (n==0) {
            return true;
        }
        ArrayList<Integer> graph[] = Create(n, prerequisites);
        return !isCycle(graph, n);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of tasks:");
        int n = sc.nextInt();
        System.out.println("Enter P:");
        int p = sc.nextInt();
        int prerequisites[][] = new int[p][2];
        System.out.println("Enter prerequisites: ");
        for (int i = 0; i < p; i++) {
            prerequisites[i][0] = sc.nextInt();
            prerequisites[i][1] = sc.nextInt();

        }
        if (Possible(n, prerequisites)) {
            System.out.println("Possible");
        } else {
            System.out.println("cannot be possible");
        }
    }
}

Comments