[Solved] SOLVED: Lab Assignment 4

Goals:1. Understanding of Warshall’s algorithm.2. Understanding of strongly connected components.Requirements:1. Write a program, based on Warshall’s algorithm with successors, to find a leader for each stronglyconnected component of a directed graph. The leader of a strongly connected component is thesmallest numbered vertex appearing in that SCC. The input will be formatted as follows:a. The first line will contain an integer V giving the number of vertices. V will not exceed 50.b. Tail and head for each edge, one edge per line. The tail and head will be in the range 0 …V – 1.c. A line with -1 -1.2. Your program’s output for each vertex i will be either 1) the fact that vertex i is a leader or 2) a pathfrom vertex i to its leader and a path from the leader to vertex i. Your program must also output theintermediate matrices from your Warshall-based technique.3. Submit your program source file on Blackboard by 10:45 am on December 4. One of the commentlines should include the compilation command used on OMEGA.Getting Started:1. Review Warshall’s algorithm with successors. Also, consider the usual transitivity diagram and howit relates to this problem.2. Test files are available on the course web page. Other cases may be used when your submissions arechecked.3. Since SCCs treat the graph as being reflexive (e.g. self-loops), each diagonal entry A[i][i] isinitialized to i. If there is an edge from i to j (i!=j), then A[i][j] is initialized to min(i,j).If there is no edge from i to j, then A[i][j] is initialized to -1 (or some other value depending onyour code).4. Based on this initialization, Warshall’s algorithm may be modified to terminate with the leader forthe SCC of vertex i stored at A[i][i].5. Your code must execute in O(V3) time.6. Static allocation (i.e. no mallocs) is allowed.7. You may modify http://ranger.uta.edu/~weems/NOTES2320/warshall.c to do this assignment.