Question

Algorithm/Implementation in Java please.

Josefine has spent the entire summer deciding what courses she wants to study at The University of Algorithms. A course takes one semester to finish (and as the super student she is, she always succeeds). Some of the courses depends on other courses, and it is therefore not allowed to take these in the same semester. If course i depends on course j, Josefine must take course i in an earlier semester than course j. She wants to finish her studies in as few semesters as possible.

Given the N courses Josefine wants to study (numbered from 1 to N), and the courses they each depend on, compute the fewest number of semesters Josefine needs to use to finish her studies. (Again, she is a super student, so she can take an unlimited number of courses each semester).

You can assume there is no cyclic dependencies in the courses Josefine has chosen.

Input format

• Line 1: The integers N and M (1 <= N <= 1.000.000) where N is the number of courses and M is the total number of dependencies.
• Line 2..M+1: Two integers X and Y meaning the course X depends on the course Y (ie. course Y must have been completed before course X)

Output format

• Line 1: The fewest number of semesters Josefine needs to use.

Restrictions

You are free to use all built-in modules/packages/functions in Java. You are not allowed to use any other modules/packages/code/etc from the internet or similar.

Sample input/output data:

Input (stdin)

5 4
1 3
2 3
4 1
4 2

Expected Output

3

Answer 1

Algorithm used here is topological sort

dfs is used top implemet topological sort .in normal dfs we push a vertex in stack then call dfs for its adjacent vertices but in this first we call dfs for its adjacent then push it in stack.and instead of using boolean visited array use integer visited array and initialise it to -1.and visited[v] will be 1+max(visited[adjacent[v]) this implies that after doing vth subject atleast max(visited[adjacent(v)] semesters will be required

In the end return max(visited of all vertices)

import java.util.*;
import java.lang.*;
import java.io.*;
class graph
{
   //number of vertices
   private int V;
   //adjacency list
   private LinkedList adj[];
   //constructor
   graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i adj[i] = new LinkedList();
}
//add edge function
void addEdge(int v,int w) { adj[v].add(w); }
void topologicalSortUtil(int v, int visited[], Stack stack)
{
Integer i;
//iterator of adjacency list of v
Iterator it = adj[v].iterator();
//x stores max value of visited of vertices adjacent to v
int x=-1;
//loop through each adjacent vertex of v
while (it.hasNext())
{
i = it.next();
//if it is not visited
if (visited[i]!=-1)
topologicalSortUtil(i, visited, stack);
//x=max(x,visited[i])
if(x x=visited[i];
  
}
//set visited[v]=1+x
//if a course is to be done at last sem its visited will be 0
//that's why while returning answer 1 is added
visited[v]=1+x;
//push v in stack
stack.push(new Integer(v));
}
int topologicalSort()
{
Stack stack = new Stack();
int visited[] = new int[V];
//initialise visited to -1
for (int i = 0; i < V; i++)
visited[i]=-1;
//call helper function for all verices which are not -1
for (int i = 0; i < V; i++)
if (visited[i] == -1)
topologicalSortUtil(i, visited, stack);
//ans stores number of semester required
int ans=-1;
for(int i=0;i {
   if(ans    ans=visited[i];
}
//as visisted is initialised with -1 so return 1+ans
return ans+1;
}
   public static void main (String[] args) throws java.lang.Exception
   {
       //take input
       Scanner sc=new Scanner(System.in);
       int n,e;
       n=sc.nextInt();
       e=sc.nextInt();
       graph g=new graph(n);
       for(int i=0;i        {
           int x,y;
           x=sc.nextInt();
           y=sc.nextInt();
           g.addEdge(x,y);
       }
       int ans=g.topologicalSort();
       System.out.println(ans);
   }
}

Ideone.com-Online Compiler and IDE>> C/C++, Java, PHP, Python, Perl and 40+ other compilers and interpreters-Google Chrome 1.9(95%) 20:27 © Algorithm/Implementati x " ideone.com-BV2D40-O BEIdeone.com-Online Com x K C https://ideone.com deone.com new code samples recent codes sign in enter your source code or insert template or sample Students and Teachers, save up to 60% on Adobe Creative Cloud. 60 ▼ 51 52 63 Lf (ansevisited[i]) ans-visited i] /as visisted is initialised with -1 so return 1+ans return ans+1: 65 56 67 58 ADS VIA CARBON ublic static void main (String[] args) throws java.lang.Exception //take input Scanner sc-new Scanner (Systen.in): int n,e n-sc.nextInto e-sc.nextinto raph g-new graph(n): or(int t-8;ce; 70 Discover > Sphere Engine API The brand new service which powers Ideone! Discover > IDE Widget widget for compling and ruming the source code in a 76 78 79 86 81 82 83 int x,y: x-sc.nextInt); y-sc.nextinto g.addEdge(x,y) nt ans-g.topologicalsort): Systen.out.println(ans): Q enter input (stdin) 5 4 2 3 We use cookies to improve our services. If you continue wilthout changing your settings, we'll assume that you are happy to recelve all cookies on Ideone OK