Problem 45462. Propagate the effects of a blockage in a chemical plant
From the perspective of flow, a chemical plant can be described by a collection of nodes and edges. Nodes are points where multiple flows meet, such as mixing points, splitting points, or plant equipment that process the flows, whereas edges are the pipe connections between the nodes.
For a chemical plant with N nodes, we can use an adjacency matrix of size N x N to represent the topology. For any adjacency matrix M,
M is always a symmetric matrix because if a pipe exists from Node i to Node j, then the same pipe exists from Node j to Node i. Also, elements in the diagonal are always zero since a node cannot connect to itself. Not shown in matrix M are the edges that connect the plant to the outside world. Here, we will simply assume that these edges exist to provide continuous flow to all the nodes.
However, the plant does not need to be fully connected; some nodes may be unreachable from other nodes by piping. Hence, if the flow was suddenly blocked inside the equipment at Node P, then it may affect only the nodes reachable from P. The effect of blockage can propagate from one node to another node if and only if there exists a series of piping that connects them (i.e., blockage effects have no regard for the direction of flow in a pipe).
Given an adjacency matrix M and the value of P, can you tell how much of the plant may be affected when a blockage occurs at Node P? Write a function that accepts variables M and P. You are ensured that 2 <= N <= 30, and 1 <= P <= N. Output a string (with no newline characters) with the format:
where P is the given value of P and X is a floating-point number rounded to 2 decimal places, which is computed as the "number of affected nodes" divided by the "total number of nodes", and given as a percentage. Note that if Node P happens to be isolated from all other nodes, then there is exactly 1 affected node.
See sample test cases:
For a visualization of the above cases, see the following figure:
Solution CommentsShow comments
Problem Recent Solvers16