All submissions for this problem are available.
Amanda is a History student. She is now doing her doctoral work in History. One of her prime works is based on transportation networks in ancient empires between their important towns. She has maps of many empires of different ages and is surprised on how intelligently the road networks were laid in these empires.
Since she doesn't have enough time to work on the maps manually, she needs the help from a computer. She feeds the computer with data from the map. Each major town of the empire is represented as a vertex. The information is laid out in the form of a 2 dimensional matrix known as the connectivity matrix which contains information whether two towns are connected by a direct link or not. i.e., the matrix element MAT[i] [j] is 1 if town i and j are connected by a direct link (i.e., There is a direct road from i to j) otherwise it is 0.
Help Amanda by writing a program which will do these tasks for her:
- Display whether the network is connected (Amanda provides the source).
- Display whether there is a cycle in the road network.
- If the network is not connected, display the towns reachable and not reachable from the source vertex in lexicographic(increasing) order of the index of the vertices.
- The roads in this problem are bidirectional. i.e., it allows flow both ways.
- A network is connected, if it is possible to reach any vertex/node of the network from any other vertex/node of the same network.
- A network is cyclic is there is a path, in the network, composed of 3 or more distinct vertices which starts and ends at the same vertex. Otherwise it is acyclic.
- Reachability is defined as follows:
- A is reachable from A. (Irrespective of the value of MAT[A][A])
- If B is reachable from A and if there is a path/link from B to C, then C is reachable from A.
- We are using 1-indexing in this problem. i.e., vertex ranges from 1 to n and not 0 to n-1
The first line contains T, the number of test cases.
Then T test cases follow. For each test case:
First line contains the number of vertices N.
The next N lines contain N space separated integers, each being either 0 or 1. This is the connectivity matrix. MAT[a] [b] = 1 means that a and b have a direct link between them else a and b have no direct link.
The next line contains a single integer SRC which is the source vertex.
For each test case:
First line should contain the test case no. Print it in this format: "TEST CASE x:" (without quotes) where x is the test case number
Next line should display whether the towns are connected. If yes, print "The graph is connected!" else print "The graph is not connected!" (without quotes)
The next line should display whether the graph is cyclic. If yes, print "Graph is cyclic!" else print "Graph is acyclic!"(without quotes)
If the towns are not connected, then display the information about the reachability of the vertices from the source in lexicographic order of index of the vertices, each line for each vertex.
For each vertex, print '1' if the vertex is reachable. Else print '0' (Both without quotes).
1 ≤ T ≤ 10
1 ≤ N ≤ 500
1 ≤ SRC ≤ N
1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1
1 0 1 0
0 1 1 1
1 1 1 0
0 1 0 1
TEST CASE 1:
The graph is not connected!
Graph is cyclic!
TEST CASE 2:
The graph is connected!
Graph is acyclic!
For test case 1:
1 is connected to 2 and 3 as MAT and MAT = 1 (We are using 1 indexing)
2 is connected to 1 and 3 MAT and MAT = 1
3 is connected to 1 and 2 MAT and MAT = 1
4 is not connected to anything. MAT = MAT = MAT = 0
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.