，GraphAdjacency Matrix。
QUESTION 1
In a di-graph, when each strongly connected component is reduced to a single node, then the resulting di-graph is a directed acyclic digraph. Explain why this is the case.
QUESTION 2
Explain why the union of strongly connected components of a digraph G does not yield G.
QUESTION 3
This question is based on the Algori City assignment created by Ulrich. The story goes like this.
Algori City’s planners love one-way streets. They say it is safer for pedestrians to cross them if cars come from one direction only. So they’ve converted a lot of their streets to one-way streets. But they have a problem: The drivers of Algori City complain that they cannot get from some parts of the city to others now. This is something the planners didn’t think of. They need help from you.
As a budding graph theorist, you know that you can represent a city’s road network as a digraph. The nodes (vertices) in the digraph are the intersections, and the arcs are the streets connecting them, such that each arc points in the direction of the one-way traffic. You also know that such a graph can be represented as an adjacency matrix or an adjacency list. So you ask the Algori
City Planning Department to give you a street map of Algori City in the form of an adjacency matrix.
The format of the matrix is something like the following.
0,1,1,0,0,0,0,... 0,0,1,0,0,0,0,... 0,1,0,0,0,0,1,...
Each row represents the node (intersection) at which the street (arc) starts. The first row is for intersection 0, the second for 1, etc., so that the nodes for the n intersections in Algori City are numbered from 0 to n-1. The non-zero entries in each row represent direct streets (arcs) going to the respective target intersection, i.e., the j-th entry in row i tells us whether you can get from intersection i to intersection j by car via a direct street (arc). So, in the example above, we can see that we can get from intersection 0 to intersection 2 via a one-way street (there is no way back), and that we can get from 1 to 2 and from 2 to 1 - presumably a two way street. Note: Each row ends with a 0 or 1 and a single newline character, not with a comma and/or dots (these are only to indicate that the row may have more entries).
Write a program matrix2list.java or matrix2list.py that reads a text file matrix.txt with an adjacency matrix in the format above and converts it into an adjacency list list.txt. You may assume that the file will be in the same directory as matrix2list.java. Your program must read the file but it must not ask for the file name (no user input please).
The list should have the following format (for the example above):
1,2,... 2,... 1,6,... ...
such that each row corresponds to the originating node (intersection) and each entry in each row gives the number of a target intersection. The target intersections in each row must be listed in increasing order. Note that there must be no comma (and no “”) after the last entry in each row. The file list.txt must not contain anything else than the list itself.
Your converter must write to the file list.txt, overwriting any previous input. Any screen output of your converter will not be marked.
You must put your name and AUID (7 or 9 digit number) in a comment at the top of the matrix2list.java or matrix2list.py file.
Your application must be delivered such that all the source files are in the top directory only - our markers will not recreate subdirectory structures for packages for you. You must not use / copy any other code examples found on the Internet.