Prerequisite Tasks

Prerequisite Tasks

  February 24, 2021    

---

Program : 

 There are a total of N tasks, labeled from 0 to N-1. Some tasks may have prerequisites, for example to do task 0 you have to first complete task 1, which is expressed as a pair: [0, 1]
Given the total number of tasks N and a list of prerequisite pairs P, find if it is possible to finish all tasks. 

 

Idea is to check if graph contains cycle or not

Code : 

 public class Graph {
        int vertices;
        LinkedList<Integer> edge[];
        Graph(int v) {
            this.vertices = v;
            edge = new LinkedList[v];
            for(int i=0;i<v;++i) {
                edge[i]=new LinkedList();
            }
        }
    }
    public boolean isPossible(int N, int[][] prerequisites)
    {
        Graph g = new Graph(N);
        for(int e[] : prerequisites) {
            g.edge[e[0]].add(e[1]);
        }
        HashSet<Integer> currentStack = new HashSet<>();
        HashSet<Integer> visited = new HashSet<>();
        for(int i =0;i<N;++i) {
        if(isCycleFound(i, g, N, currentStack, visited))
            return false;
        }
        return true;
    }
    public boolean isCycleFound(int start, Graph g, int n,
                                HashSet<Integer> currentStack,
                                HashSet<Integer> visited) {
        if(currentStack.contains(start)) return true;
        if(visited.contains(start)) return false;
        visited.add(start);
        currentStack.add(start);
        boolean response = false;
        // System.out.println("Start is"+ start);
        for(int edge : g.edge[start]) {
            // System.out.println("Looking for edge"+ edge);
                response |= isCycleFound(edge, g, n, currentStack, visited);
        }
        currentStack.remove(start);
        return response;
    }