Vizualizare sursă pentru „DSA Homework 5”

= Data Centers =

Little John is all grown up now and working in a high tech data center. One day, as he got to work, he finds out that hackers attacked his network and managed to disable some of the servers. A disabled server can't route data in or out, so it behaves as all links to and from it are disabled. Some of the remaining servers are critical to data access within his company and he wants to know if there is still a route for the data between them.

Help Little John write a program to find out if those servers are still linked.

== Requirement ==

Given a number of servers N and an adjacency matrix NxN specifying the links between those servers, a number K of failed servers, and pair of servers (i, j), specify if there is still a route between server i and server j.

== Input Data ==

A file called ''data_center.in'', containing the number of servers N on the first line and N x N subsequent values, defining the adjacency matrix, arranged in a square, on N lines, followed by the number K of failed servers, K values specifying the servers on the following line, and the pair (i, j) on the last line.

== Output Data ==

A file called ''data_center.out'', containing the value 0 if there is no route between the two specified servers and 1 if there is.

== Restrictions ==
1 ≤ K ≤ N ≤ 1000

== Examples ==

{| class="wikitable"
|- bgcolor="#ddeeff" align="left"
|'''Input''' || '''Output''' || '''Comments'''
|- bgcolor="#ddffdd" align="left"
|
<pre style="font-size:12px">
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 1
0 0 1 1 0
1
2
0 4
</pre>
|
<pre style="font-size:12px">
0
</pre>
|
The data center has 5 nodes. There is only 1 failed node: node 2. The critical servers are 0 and 4 and since there is no route between them, the result is 0.
|-  bgcolor="#ddffdd" align="left"
|<pre style="font-size:12px">
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 1
0 0 1 1 0
2
1 3
0 4
</pre>
|
<pre style="font-size:12px">
1
</pre>
|
The data center has 5 nodes. There are 2 failed nodes: nodes 1 and 3. The critical servers are 0 and 4 and since there is now a route between them, the result is 1.
|}