376. Safe Electrical Wire Configurations

Safe Electrical Wire Configurations

An electrical network has power stations numbered from 0 through n - 1. Each station has one electrical wire connecting it to another station.

Every wire has a one-way controller that can allow current to flow in either direction. A configuration is safe if the directed wires do not form any cycle.

Count the number of safe electrical wire configurations.

Safe Electrical Wire Configurations

Implement the following method:

int countSafeWireLayouts(List<Integer> connectedStation)

The number of power stations is connectedStation.size().
Wire i connects station i with station connectedStation.get(i).
The controller on wire i may allow current to flow from station i to connectedStation.get(i), or in the opposite direction.
The method returns the number of safe configurations modulo 1,000,000,007.

Rules

Every electrical wire must be assigned exactly one current direction.
A configuration is safe when it contains no directed cycle.
Electrical wires are identified by their list positions.
Two wires remain different even when they connect the same pair of stations.
Two configurations are different if at least one wire has a different current direction.

Constraints

2 ≤ connectedStation.size() ≤ 200,000
0 ≤ connectedStation.get(i) < connectedStation.size()
connectedStation.get(i) != i
connectedStation never contains null values.

Examples

Example 1

countSafeWireLayouts( connectedStation = List.of(1, 2, 3, 0, 1, 4) )

Output: 56

The first four wires form a ring. They have 14 safe current assignments. Each of the other two wires may carry current in either direction, giving 14 × 2² = 56 configurations.

Example 2

countSafeWireLayouts( connectedStation = List.of(1, 0, 3, 4, 2, 4, 5) )

Output: 48

The network contains one ring of two wires and another ring of three wires. The remaining two wires may independently carry current in either direction. Therefore, there are 2 × 6 × 2² = 48 safe configurations.

Example 3

countSafeWireLayouts( connectedStation = List.of(1, 2, 3, 4, 5, 0) )

Output: 62

All six wires form one ring. Of the 64 possible direction assignments, exactly two create a directed cycle. Therefore, 62 configurations are safe.

Example 4

countSafeWireLayouts( connectedStation = List.of(1, 0, 3, 2, 5, 4) )

Output: 8

The electrical network contains three separate two-wire rings. Each ring has two safe direction assignments, producing 2 × 2 × 2 = 8 safe configurations.