CactusCount | Topcoder Archive

Problem Statement

A vertex cactus is a connected undirected graph such that each vertex belongs to at most one simple cycle. A simple cycle is a cycle that doesn't pass through any vertex more than once. For example, the graph pictured below is a vertex cactus:

You are given an int n, the number of vertices in a graph G. The vertices are numbered from 1 to n. The edges in G are given in the String[] edges. Concatenate the elements of edges to get a comma-separated list of integer pairs. The integers in each pair are separated by a space. The pair "i j" (quotes for clarity) means that there is an edge between vertices i and j. Return the number of connected components of G that are vertex cacti.

Definition

Class:: CactusCount
Method:: countCacti
Parameters:: int, String[]
Returns:: int
Method signature:: int countCacti(int n, String[] edges)
(be sure your method is public)

Notes

A connected component of a graph G is a set of vertices such that each pair of vertices in the set is connected by a path, and no vertex outside the set is connected to any vertex within the set.

Constraints

n will be between 1 and 200, inclusive.
edges will contain between 0 and 50 elements, inclusive.
Each element of edges will contain between 1 and 50 characters, inclusive.
When concatenated, edges will contain a comma separated list of integer pairs.
The integers within each pair will be separated by a space.
The integers within each pair will be distinct.
Each integer will be between 1 and n, inclusive, with no leading zeroes.
Every pair of vertices will be connected by at most one edge.

Examples

```
3
```
```
{"1 2,1 3,2 3"}
```
```
Returns: 1
```
One cycle is a vertex cactus.
```
10
```
```
{}
```
```
Returns: 10
```
Here each vertex is a component by itself. A graph with one vertex is a vertex cactus.
```
5
```
```
{"1 2,3 4,4 5"}
```
```
Returns: 2
```
Both components are trees. A tree is a vertex cactus.
```
17
```
```
{"1 2,2 3,3 4,4 5,5 3,1 3,6 7,7 8,6 8,8 9,9 1",
 "0,10 11,11 9,12 13,14 15,15 16,16 17,14 17,14 16"}
```
```
Returns: 2
```
Here are two cacti and two non-cacti. The component with vertices 1, 2, 3, 4 and 5 is not a vertex cactus because vertex 3 belongs to two cycles: 1-2-3 and 3-4-5. The component with vertices 14, 15, 16 and 17 is not a vertex cactus either. Vertex 14, for example, belongs to more than one cycle.

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.