LANConnectivity | Topcoder Archive

Problem Statement

Extended Local Area Networks are built by connecting routing devices called switches. These switches route transfers between different nodes on the network. To avoid routing loops, switches have a process through which they elect a master switch and build a routing tree. A routing tree is a designated set of connections that directly or indirectly connect every node to every other node, without forming any cycles. Two nodes are indirectly connected if some sequence of direct connections will take you from one node to the other. A cycle is a sequence of distinct connections leading from one node back to itself.

You will be given a String[] connects representing the direct connections between the switches of the network. Element i (0-based) of connects will represent switch i of the network. Each element of connects will be a single space-delimited list of integers. If element i contains the integer j it means that switches i and j are directly connected. The connections are full duplex. This means that element i will contain integer j if and only if element j contains integer i. Your method will return the total number of routing trees that are possible. Two routing trees are distinct if they differ in terms of any of the direct connections used.

Definition

Class:: LANConnectivity
Method:: numConnects
Parameters:: String[]
Returns:: int
Method signature:: int numConnects(String[] connects)
(be sure your method is public)

Constraints

connects will contain between 1 and 20 elements inclusive
Each element of connects will contain between 1 and 50 characters inclusive
Each element of connects will be a single space delimited list of distinct integers with no extra leading zeros
Each element of connects will have no leading or trailing spaces
Each integer in each element of connects must be between 0 and (size of connects-1) inclusive
No element of connects will contain repeated values
Element i of connects contains integer j if and only if element j of connects contains integer i
No element will contains its own index as a term
There will be at most 18 distinct connections

Examples

```
{"1 2 3","0 4","0 4","0 4","1 2 3"}
```
```
Returns: 12
```
The configuration looks something like: 1 / \ 0-2-4 \ / 3 Lets call the "middle nodes" 1, 2, and 3. Since 0 and 4 must be connected, one of the middle nodes must have 2 connections in any tree. Thus, we have 3 choices for which middle node should have 2 connections. After choosing a middle node, we then have 2 remaining middle nodes, each of which must have 1 connection. Since each has a choice between connecting with 0 or 4 we have: 3 * 2 * 2 = 12 possible connections.
```
{"1","0"}
```
```
Returns: 1
```
Only one routing tree is possible containing the single edge.
```
{"1 3","0 2","1 3","0 2"}
```
```
Returns: 4
```
Any of the 4 edges can be excluded leaving a possible routing tree.

{"1 2 3 4 5","0 2 3 4 5","0 1 3 4 5",
 "0 1 2 4 5","0 1 2 3 5","0 1 2 3 4"}

Returns: 1296

```
{"1","0","3","2"}
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.