In this assignment, you are already given an algorithm for topological sorting. 1. Run the topological sorting algorithm on Graph g1 defined in main. Print and note down the result somewhere. [10 pts] 2. For a topological sort to exist, the graph must not contain any cycles. Modify topologicalSort() method any way you like to handle such cases. The method now must print A cycle detected! in such a case. Test your code on Graph g2. [30 pts] 3. Current implementation of topologicalSort() uses queues. Implement a new method called topologicalSortStack()so that the underlying data structure is now a stack. This new method must use stack methods such as push() and pop() and it must also handle cases with cycles. [30 pts] (Note: You can use the default Stack implementation of Java for this method.) 4. Test this modified version with Graph g1. Is the result different from before? Does it mean your code is wrong if there is a difference? Explain the results and discuss in detail in your own words as a comment in your source code. [30 pts] 

// A Java program to print topological sorting of a graph using indegrees // src: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ import java.util.*; //Class to represent a graph class Graph { int V;// No. of vertices //An Array of List which contains //references to the Adjacency List of //each vertex List  adj[]; public Graph(int V)// Constructor { this.V = V; adj = new ArrayList[V]; for(int i = 0; i < V; i++) adj[i]=new ArrayList(); } // function to add an edge to graph public void addEdge(int u,int v) { adj[u].add(v); } // prints a Topological Sort of the complete graph public void topologicalSort() { // Create a array to store indegrees of all // vertices. Initialize all indegrees as 0. int indegree[] = new int[V]; // Traverse adjacency lists to fill indegrees of // vertices. This step takes O(V+E) time for(int i = 0; i < V; i++) { ArrayList temp = (ArrayList) adj[i]; for(int node : temp) { indegree[node]++; } } // Create a queue and enqueue all vertices with // indegree 0 Queue q = new LinkedList(); for(int i = 0;i < V; i++) { if(indegree[i]==0) q.add(i); } // Initialize count of visited vertices int cnt = 0; // Create a vector to store result (A topological // ordering of the vertices) Vector  topOrder=new Vector(); while(!q.isEmpty()) { // Extract front of queue (or perform dequeue) // and add it to topological order int u=q.poll(); topOrder.add(u); // Iterate through all its neighboring nodes // of dequeued node u and decrease their in-degree // by 1 for(int node : adj[u]) { // If in-degree becomes zero, add it to queue if(--indegree[node] == 0) q.add(node); } cnt++; } // Print topological order for(int i : topOrder) { System.out.print(i+" "); } System.out.println(); } }  

class Main { public static void main(String args[]) { // A graph Graph g1=new Graph(6); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(2, 3); g1.addEdge(3, 4); g1.addEdge(5, 2); g1.addEdge(5, 4); // A graph that contains a cycle Graph g2=new Graph(6); g2.addEdge(1, 2); g2.addEdge(2, 5); g2.addEdge(5, 0); g2.addEdge(5, 1); g2.addEdge(3, 4); g2.addEdge(4, 5); // Question 4: Comment here } }