Connection Status:
Competition Arena > CactusCount

CactusCount

SRM 419 · 2008-09-24 · by andrewzta

SRM 419 · 2008-09-24 · by andrewzta · Graph Theory, String Parsing
Class Name: CactusCount
Return Type: int
Method Name: countCacti
Arg Types: (int, vector<string>)
Problem Statement

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.

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
0)
3
{"1 2,1 3,2 3"}
Returns: 1

One cycle is a vertex cactus.

1)
10
{}
Returns: 10

Here each vertex is a component by itself. A graph with one vertex is a vertex cactus.

2)
5
{"1 2,3 4,4 5"}
Returns: 2

Both components are trees. A tree is a vertex cactus.

3)
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.

4)
200
{ "1 2,2 3,1 3,3 4,4 5,5 6,4 6,6 7,7 8,8 9,7 9,9 10,1", "0 11,11 12,10 12,12 13,13 14,14 15,13 15,15 16,16 ", "17,17 18,16 18,18 19,19 20,20 21,19 21,21 22,22 23", ",23 24,22 24,24 25,25 26,26 27,25 27,27 28,28 29,2", "9 30,28 30,30 31,31 32,32 33,31 33,33 34,34 35,35 ", "36,34 36,36 37,37 38,38 39,37 39,39 40,40 41,41 42", ",40 42,42 43,43 44,44 45,43 45,45 46,46 47,47 48,4", "6 48,48 49,49 50,50 51,49 51,51 52,52 53,53 54,52 ", "54,54 55,55 56,56 57,55 57,57 58,58 59,59 60,58 60", ",60 61,61 62,62 63,61 63,63 64,64 65,65 66,64 66,6", "6 67,67 68,68 69,67 69,69 70,70 71,71 72,70 72,72 ", "73,73 74,74 75,73 75,75 76,76 77,77 78,76 78,78 79", ",79 80,80 81,79 81,81 82,82 83,83 84,82 84,84 85,8", "5 86,86 87,85 87,87 88,88 89,89 90,88 90,90 91,91 ", "92,92 93,91 93,93 94,94 95,95 96,94 96,96 97,97 98", ",98 99,97 99,99 100,100 101,101 102,100 102,102 10", "3,103 104,104 105,103 105,105 106,106 107,107 108,", "106 108,108 109,109 110,110 111,109 111,111 112,11", "2 113,113 114,112 114,114 115,115 116,116 117,115 ", "117,117 118,118 119,119 120,118 120,120 121,121 12", "2,122 123,121 123,123 124,124 125,125 126,124 126,", "126 127,127 128,128 129,127 129,129 130,130 131,13", "1 132,130 132,132 133,133 134,134 135,133 135,135 ", "136,136 137,137 138,136 138,138 139,139 140,140 14", "1,139 141,141 142,142 143,143 144,142 144,144 145,", "145 146,146 147,145 147,147 148,148 149,149 150,14", "8 150,150 151,151 152,152 153,151 153,153 154,154 ", "155,155 156,154 156,156 157,157 158,158 159,157 15", "9,159 160,160 161,161 162,160 162,162 163,163 164,", "164 165,163 165,165 166,166 167,167 168,166 168,16", "8 169,169 170,170 171,169 171,171 172,172 173,173 ", "174,172 174,174 175,175 176,176 177,175 177,177 17", "8,178 179,179 180,178 180,180 181,181 182,182 183,", "181 183,183 184,184 185,185 186,184 186,186 187,18", "7 188,188 189,187 189,189 190,190 191,191 192,190 ", "192,192 193,193 194,194 195,193 195,195 196,196 19", "7,197 198,196 198"}
Returns: 3

Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CactusCount with a public method int countCacti(int n, vector<string> edges) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous