FindTriangles | Topcoder Archive

Problem Statement

Within a wireless network there are often fixed beacons that service many roaming clients. One measure of the connectedness of such a network is the number of triangles amongst the beacons. A triangle is a set of 3 nodes that are all directly connected to one another. You will be given a String[] connections listing the direct connections amongst the beacons in the network. Each element will have the form "beaconNum beaconNum" where each beaconNum is a number between 0 and 100 inclusive. For example, "17 5" will mean that beacon 17 and beacon 5 are directly connected. All connections are bidirectional. Return the number of distinct triangles in the network described by connections. Two triangles are distinct if one contains a beacon that the other doesn't.

Definition

Class:: FindTriangles
Method:: howMany
Parameters:: String[]
Returns:: int
Method signature:: int howMany(String[] connections)
(be sure your method is public)

Constraints

connections will contain between 0 and 50 elements inclusive.
Each element of connections will have the form "beaconNum beaconNum". Each beaconNum is an integer between 0 and 100 inclusive with no extra leading zeros. Within a single element of connections, the two beaconNums will be distinct.
No two elements of connections will represent the same connection. In other words, if one element of connections is "a b" then neither "a b" nor "b a" can occur again in connections.

Examples

```
{"0 10","10 20","0 20"}
```
```
Returns: 1
```
A single triangle. 20 / \ / \ 0----10
```
{"0 10","10 20","0 20","1 0","10 1"}
```
```
Returns: 2
```
A second triangle. 20 / \ / \ 0----10 \ / \ / 1
```
{"0 10","10 20","0 20","1 0","10 1","20 1"}
```
```
Returns: 4
```
Now there are 4. 20 /|\ / | \ 0----10 \ | / \|/ 1
```
{"0 1","1 2","2 0","3 4","4 5","5 3"}
```
```
Returns: 2
```
Two disjoint triangles. 0 3 / \ / \ / \ / \ 1-----2 4-----5

{"0 1","1 2","2 3","3 4","4 5","5 0",
 "10 20","90 100","1 99","15 27"}

Returns: 0

Many connections, but no triangles.

```
{}
```
```
Returns: 0
```
No connections.

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.