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 strongly
connected component of a directed graph. The leader of a strongly connected component is the
smallest 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 path
from vertex i to its leader and a path from the leader to vertex i. Your program must also output the
intermediate matrices from your Warshall-based technique.
3. Submit your program source file on Blackboard by 10:45 am on December 4. One of the comment
lines should include the compilation command used on OMEGA.
Getting Started:
1. Review Warshall’s algorithm with successors. Also, consider the usual transitivity diagram and how
it relates to this problem.
2. Test files are available on the course web page. Other cases may be used when your submissions are
checked.
3. Since SCCs treat the graph as being reflexive (e.g. self-loops), each diagonal entry A[i][i] is
initialized 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 on
your code).
4. Based on this initialization, Warshall’s algorithm may be modified to terminate with the leader for
the 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.
