Attack Cities and Conquer

Computer Science Level 5

As Sheldor the conqueror, you're supposed to conquer the kingdom of Wonder-blunder-berg , which happens to be a collection of cities connected with roads.

Your first plan is to attack cities, which when blocked, splits the kingdom into parts that cannot communicate with each other.

For example,

In the above kingdom, the multicolored cities, when removed, disconnect the road network.

This is the Adjacency List of the road network of Wonderblunderberg showing which city has a direct road to which other city.

How many such vulnerable cities exist in the kingdom?

Clarification: A component is a maximal set of cities such that there is a walk between any two cities of the set. A vulnerable city is a city which when, along with its roads, removed, increases the number of components.

The title is just a title, it has nothing to do with the algorithm you'll need.

Image Credit: Wikimedia Zyqqh .

The answer is 28.

3 solutions

Agnishom Chattopadhyay
Jul 22, 2016

In Graph Theory, we call such vulnerable points Cut Vertices or Articulation Points . In the following analysis, we'll assume that the graph is connected. If it is not, we run the algorithm separately for each component.

We could explore our graph using Depth First Search . While doing so, we could think of a spanning tree called the DFS tree . In the DFS tree ,

$v$ is a child of $u$ if we arrived at $v$ from $u$ while exploring the graph.
The root is the vertex at which the DFS exploration began.
If $v$ is a child of $u$ , then $depth[v] = depth[u] + 1$

The non-tree edges are classified into forward edges, backward edges and cross edge depending on the depths they connect.

Consider this graph and its corresponding DFS tree

1 -> 2 -> 3 -> 4
          |
          v
     7 <- 6 -> 5
          |
          V
          8

Backedges: 4 -> 2, 5 -> 1

We define a concept called the lowpoint of a vertex. For each vertex $v$ , the lowest depth of neighbors of all descendants of $v$ in the DFS tree is $lowpoint(v)$ . For example, the lowpoint of $2$ in this graph is $d=1$ , since one of its descendants have a backedge to a vertex at depth 1.

Now lets take a graph and draw its DFS tree. If there is a child $v$ of a vertex $u$ such that there is a back-edge from $v$ to $u$ or its ancestors, then $v$ is not an articulation vertex. That is because, even if $v$ were removed, that backedge would still be keeping the graph connected. So, if $v$ is a (non-root) articulation point, $v$ has a child such that $lowpoint[y] \geq depth[v]$ .

The root needs to be dealt separately. The root is an articulation point iff it has more than one children.

Alright, time for action.

adjList = [[],[14,167],[111,137,160],[31,69,218],[8,14,154,228],[25,92,150,190],[231],[211,223],[4,69,155],[49,161,213,243],[40,172,202],[63,70,101,256],[61,157,261],[173,247],[1,4,77,241,264],[35,138,178],[49,57,250],[],[58,74,150,177,182,201,273],[21,117,244],[54,63],[19,195,229,237],[133,142,188],[48,50,117,155,189,213],[115],[5,85,190,203],[139],[128,130,166,245],[59,133,170],[48],[50,59,236],[3,43,62,151],[192,218,262,267],[61],[51,53,96],[15,59,173,179,182,210],[53,137,143,229],[135,203,265],[52,256,272],[207,233,244],[10,67,79,149],[43,68,119,127,230],[56,62,163],[31,41,73,106,255],[45,224,233,251],[44,70,87,131,175,205,268,272],[50,104,137,165,242],[271,274],[23,29,55,70],[9,16,100,154,226,268],[23,30,46,103,128,216,265],[34,68,230],[38,194,258],[34,36,66,133,150,210,234],[20,174,181,191],[48,246],[42,97,193],[16,114],[18,175,210],[28,30,35,93,100,251,262],[130,149,167],[12,33,115,132,147,214],[31,42,89,151,235],[11,20,110,238,253],[91,104],[72,154],[53,116,235,238],[40,192,236,273],[41,51,106,166],[3,8,193,268],[11,45,48,117,146],[125,224],[65,218,253,262],[43,120,192,238],[18,133,193,197],[],[213],[14,200,254],[96,117,188],[40,91],[167,184,223,236,268],[165],[165,178,182,183,195],[97,274],[152,157],[25,122,162,222],[113,116,209,220,268],[45,99,164,257],[216],[62,101,222,257],[108,252],[64,79,118,162,271],[5,174,269],[59],[96,136,185],[155,160,169,210],[34,78,94,116],[56,83,216],[123,130],[87,103,131,214],[49,59,160,225,254],[11,89,112,138,154,168,260],[130,185,191],[50,99,164,217],[46,64,148,172,202,203],[138,168,217],[43,68,231],[184,187,224],[90,156,177],[247],[63,144,165,257,271],[2,119,202,217,267],[101,140,248,251],[86,129,140,165,218,224],[57,163,190],[24,61],[66,86,96],[19,23,70,78,218,234,264],[91,129,194],[41,111,162,225],[73,221,267],[225],[85,215,245],[98,131,168],[231],[71,204,237],[137,141,158,165],[41,128,135,262,273],[27,50,127,139,266],[113,118,133,182],[27,60,98,102,202,268],[45,99,123,167,238],[61],[22,28,53,74,129,175,235],[],[37,127,159],[94,154,184,242,259,271],[2,36,46,126,226,232],[15,101,105,179,212],[26,128,221],[112,113],[126,224,243,256],[22],[36,168,192,222,234,241],[110,192,211,232,255],[],[70,244],[61,170,174,208,214,256],[104,269],[40,60,268],[5,18,53,156,176,192],[31,62,191,269],[84,185,198],[],[4,49,65,101,136],[8,23,95],[108,150,184],[12,84],[126],[135,196],[2,95,100,233,261],[9,247],[85,91,119,169,240,247],[42,114],[87,103,185],[46,81,82,110,113,126,176,203,253],[27,68],[1,60,80,131,246,253],[101,105,123,143,220],[95,162,192],[28,147,274],[229],[10,104,206],[13,35,200],[54,92,147,196,205,209],[45,58,133,187,237],[150,165],[18,108,237,249,251],[15,82],[35,138,234],[187],[54,221,244],[18,35,82,129],[82],[80,107,136,156,232],[94,102,152,164,192],[245,251],[107,175,180],[22,78],[23,238,268],[5,25,114],[54,102,151],[32,67,73,143,144,150,169,185,246],[56,69,74,231,272,274],[52,118,247,255],[21,82,212,226,237,245,254],[159,174,218],[74,248],[152],[],[77,173,233,241],[18],[10,104,111,130,211,234],[25,37,104,165,246],[125],[45,174],[172,249],[39],[147,217],[86,174,235],[35,53,58,95],[7,144,202,227,234],[138,195,261],[9,23,76],[61,99,147],[122],[50,88,97],[103,105,111,208],[3,32,72,113,117,196,234,250,258],[254],[86,168],[120,139,181],[85,89,143],[7,80],[44,71,107,113,141],[100,119,121],[49,137,195],[211,241,243],[4],[21,36,171],[41,51,270],[6,106,124,193],[137,144,184],[39,44,160,200],[53,117,143,179,202,211,218,239],[62,66,133,209,240],[30,67,80,270],[21,125,175,177,195],[63,66,73,131,189],[234],[162,235],[14,143,200,227],[46,136,265],[9,141,227],[19,39,146,181,251,258],[27,122,186,195,266],[55,167,192,203,250,273],[13,109,161,162,194],[112,197],[177,206,250],[16,218,246,249],[44,59,112,177,186,244],[90],[63,72,165,167,254,264],[77,100,195,219,253,263],[43,144,194],[11,38,141,147],[87,89,110],[52,218,244],[136],[101],[12,160,212],[32,59,72,127,265],[254],[14,117,253],[37,50,242,262],[128,245],[32,111,120],[45,49,69,80,86,130,149,189],[92,148,151],[230,236],[47,91,110,136],[38,45,193,273],[18,67,127,246,272],[47,83,170,193]]

def getArticulationPoints(adjList):
    visited = [False for i in xrange(len(adjList))]
    depth = [0 for i in xrange(len(adjList))]
    low = [0 for i in xrange(len(adjList))]
    parent = [0 for i in xrange(len(adjList))]
    articulations = set()
    def rec(u, d):
        visited[u] = True
        depth[u] = d
        low[u] = d
        childCount = 0
        for v in adjList[u]:
            if not visited[v]:
                parent[v] = u
                rec(v, d+1)
                childCount += 1
                if low[v] >= depth[u] and parent[u] != 0:
                    articulations.add(u)
                low[u] = min(low[u], low[v])
            elif v != parent[u]:
                low[u] = min(low[u], depth[v])
        if parent[u] == 0 and childCount > 1:
            articulations.add(u)
    for u in xrange(len(adjList)):
        if not visited[u]:
            rec(u,1)
    return articulations
print len(getArticulationPoints(adjList))

@Agnishom Chattopadhyay : In your "Carrot" problem file, some of the x-coordinates have value 1000. Is that an error?

Snehal Shekatkar - 4 years, 10 months ago

Yes, can you disregard those points and let me know what answer you are getting?

Agnishom Chattopadhyay - 4 years, 10 months ago

@Agnishom Chattopadhyay : Sure. If I could at all solve it ;)

Snehal Shekatkar - 4 years, 10 months ago

@Snehal Shekatkar – I am sorry about the error. I will try to fix this soon.

Agnishom Chattopadhyay - 4 years, 10 months ago

Bobbym None
Jul 22, 2016

Hi; Only Agnishom could get me to think about graphs.

feebee[rul_] := Module[{f = First[rul], h = Last[rul]},
   (f -> #) & /@ h];

rules = {1 -> {14, 167}, 2 -> {111, 137, 160}, 3 -> {31, 69, 218}, 
   4 -> {8, 14, 154, 228}, 5 -> {25, 92, 150, 190}, 6 -> {231}, 
   7 -> {211, 223}, 8 -> {4, 69, 155}, 9 -> {49, 161, 213, 243}, 
   10 -> {40, 172, 202}, 11 -> {63, 70, 101, 256}, 
   12 -> {61, 157, 261}, 13 -> {173, 247}, 14 -> {1, 4, 77, 241, 264},
    15 -> {35, 138, 178}, 16 -> {49, 57, 250}, 17 -> {}, 
   18 -> {58, 74, 150, 177, 182, 201, 273}, 19 -> {21, 117, 244}, 
   20 -> {54, 63}, 21 -> {19, 195, 229, 237}, 22 -> {133, 142, 188}, 
   23 -> {48, 50, 117, 155, 189, 213}, 24 -> {115}, 
   25 -> {5, 85, 190, 203}, 26 -> {139}, 27 -> {128, 130, 166, 245}, 
   28 -> {59, 133, 170}, 29 -> {48}, 30 -> {50, 59, 236}, 
   31 -> {3, 43, 62, 151}, 32 -> {192, 218, 262, 267}, 33 -> {61}, 
   34 -> {51, 53, 96}, 35 -> {15, 59, 173, 179, 182, 210}, 
   36 -> {53, 137, 143, 229}, 37 -> {135, 203, 265}, 
   38 -> {52, 256, 272}, 39 -> {207, 233, 244}, 
   40 -> {10, 67, 79, 149}, 41 -> {43, 68, 119, 127, 230}, 
   42 -> {56, 62, 163}, 43 -> {31, 41, 73, 106, 255}, 
   44 -> {45, 224, 233, 251}, 
   45 -> {44, 70, 87, 131, 175, 205, 268, 272}, 
   46 -> {50, 104, 137, 165, 242}, 47 -> {271, 274}, 
   48 -> {23, 29, 55, 70}, 49 -> {9, 16, 100, 154, 226, 268}, 
   50 -> {23, 30, 46, 103, 128, 216, 265}, 51 -> {34, 68, 230}, 
   52 -> {38, 194, 258}, 53 -> {34, 36, 66, 133, 150, 210, 234}, 
   54 -> {20, 174, 181, 191}, 55 -> {48, 246}, 56 -> {42, 97, 193}, 
   57 -> {16, 114}, 58 -> {18, 175, 210}, 
   59 -> {28, 30, 35, 93, 100, 251, 262}, 60 -> {130, 149, 167}, 
   61 -> {12, 33, 115, 132, 147, 214}, 62 -> {31, 42, 89, 151, 235}, 
   63 -> {11, 20, 110, 238, 253}, 64 -> {91, 104}, 65 -> {72, 154}, 
   66 -> {53, 116, 235, 238}, 67 -> {40, 192, 236, 273}, 
   68 -> {41, 51, 106, 166}, 69 -> {3, 8, 193, 268}, 
   70 -> {11, 45, 48, 117, 146}, 71 -> {125, 224}, 
   72 -> {65, 218, 253, 262}, 73 -> {43, 120, 192, 238}, 
   74 -> {18, 133, 193, 197}, 75 -> {}, 76 -> {213}, 
   77 -> {14, 200, 254}, 78 -> {96, 117, 188}, 79 -> {40, 91}, 
   80 -> {167, 184, 223, 236, 268}, 81 -> {165}, 
   82 -> {165, 178, 182, 183, 195}, 83 -> {97, 274}, 84 -> {152, 157},
    85 -> {25, 122, 162, 222}, 86 -> {113, 116, 209, 220, 268}, 
   87 -> {45, 99, 164, 257}, 88 -> {216}, 89 -> {62, 101, 222, 257}, 
   90 -> {108, 252}, 91 -> {64, 79, 118, 162, 271}, 
   92 -> {5, 174, 269}, 93 -> {59}, 94 -> {96, 136, 185}, 
   95 -> {155, 160, 169, 210}, 96 -> {34, 78, 94, 116}, 
   97 -> {56, 83, 216}, 98 -> {123, 130}, 99 -> {87, 103, 131, 214}, 
   100 -> {49, 59, 160, 225, 254}, 
   101 -> {11, 89, 112, 138, 154, 168, 260}, 102 -> {130, 185, 191}, 
   103 -> {50, 99, 164, 217}, 104 -> {46, 64, 148, 172, 202, 203}, 
   105 -> {138, 168, 217}, 106 -> {43, 68, 231}, 
   107 -> {184, 187, 224}, 108 -> {90, 156, 177}, 109 -> {247}, 
   110 -> {63, 144, 165, 257, 271}, 111 -> {2, 119, 202, 217, 267}, 
   112 -> {101, 140, 248, 251}, 113 -> {86, 129, 140, 165, 218, 224}, 
   114 -> {57, 163, 190}, 115 -> {24, 61}, 116 -> {66, 86, 96}, 
   117 -> {19, 23, 70, 78, 218, 234, 264}, 118 -> {91, 129, 194}, 
   119 -> {41, 111, 162, 225}, 120 -> {73, 221, 267}, 121 -> {225}, 
   122 -> {85, 215, 245}, 123 -> {98, 131, 168}, 124 -> {231}, 
   125 -> {71, 204, 237}, 126 -> {137, 141, 158, 165}, 
   127 -> {41, 128, 135, 262, 273}, 128 -> {27, 50, 127, 139, 266}, 
   129 -> {113, 118, 133, 182}, 130 -> {27, 60, 98, 102, 202, 268}, 
   131 -> {45, 99, 123, 167, 238}, 132 -> {61}, 
   133 -> {22, 28, 53, 74, 129, 175, 235}, 134 -> {}, 
   135 -> {37, 127, 159}, 136 -> {94, 154, 184, 242, 259, 271}, 
   137 -> {2, 36, 46, 126, 226, 232}, 138 -> {15, 101, 105, 179, 212},
    139 -> {26, 128, 221}, 140 -> {112, 113}, 
   141 -> {126, 224, 243, 256}, 142 -> {22}, 
   143 -> {36, 168, 192, 222, 234, 241}, 
   144 -> {110, 192, 211, 232, 255}, 145 -> {}, 146 -> {70, 244}, 
   147 -> {61, 170, 174, 208, 214, 256}, 148 -> {104, 269}, 
   149 -> {40, 60, 268}, 150 -> {5, 18, 53, 156, 176, 192}, 
   151 -> {31, 62, 191, 269}, 152 -> {84, 185, 198}, 153 -> {}, 
   154 -> {4, 49, 65, 101, 136}, 155 -> {8, 23, 95}, 
   156 -> {108, 150, 184}, 157 -> {12, 84}, 158 -> {126}, 
   159 -> {135, 196}, 160 -> {2, 95, 100, 233, 261}, 161 -> {9, 247}, 
   162 -> {85, 91, 119, 169, 240, 247}, 163 -> {42, 114}, 
   164 -> {87, 103, 185}, 
   165 -> {46, 81, 82, 110, 113, 126, 176, 203, 253}, 166 -> {27, 68},
    167 -> {1, 60, 80, 131, 246, 253}, 
   168 -> {101, 105, 123, 143, 220}, 169 -> {95, 162, 192}, 
   170 -> {28, 147, 274}, 171 -> {229}, 172 -> {10, 104, 206}, 
   173 -> {13, 35, 200}, 174 -> {54, 92, 147, 196, 205, 209}, 
   175 -> {45, 58, 133, 187, 237}, 176 -> {150, 165}, 
   177 -> {18, 108, 237, 249, 251}, 178 -> {15, 82}, 
   179 -> {35, 138, 234}, 180 -> {187}, 181 -> {54, 221, 244}, 
   182 -> {18, 35, 82, 129}, 183 -> {82}, 
   184 -> {80, 107, 136, 156, 232}, 185 -> {94, 102, 152, 164, 192}, 
   186 -> {245, 251}, 187 -> {107, 175, 180}, 188 -> {22, 78}, 
   189 -> {23, 238, 268}, 190 -> {5, 25, 114}, 191 -> {54, 102, 151}, 
   192 -> {32, 67, 73, 143, 144, 150, 169, 185, 246}, 
   193 -> {56, 69, 74, 231, 272, 274}, 194 -> {52, 118, 247, 255}, 
   195 -> {21, 82, 212, 226, 237, 245, 254}, 196 -> {159, 174, 218}, 
   197 -> {74, 248}, 198 -> {152}, 199 -> {}, 
   200 -> {77, 173, 233, 241}, 201 -> {18}, 
   202 -> {10, 104, 111, 130, 211, 234}, 
   203 -> {25, 37, 104, 165, 246}, 204 -> {125}, 205 -> {45, 174}, 
   206 -> {172, 249}, 207 -> {39}, 208 -> {147, 217}, 
   209 -> {86, 174, 235}, 210 -> {35, 53, 58, 95}, 
   211 -> {7, 144, 202, 227, 234}, 212 -> {138, 195, 261}, 
   213 -> {9, 23, 76}, 214 -> {61, 99, 147}, 215 -> {122}, 
   216 -> {50, 88, 97}, 217 -> {103, 105, 111, 208}, 
   218 -> {3, 32, 72, 113, 117, 196, 234, 250, 258}, 219 -> {254}, 
   220 -> {86, 168}, 221 -> {120, 139, 181}, 222 -> {85, 89, 143}, 
   223 -> {7, 80}, 224 -> {44, 71, 107, 113, 141}, 
   225 -> {100, 119, 121}, 226 -> {49, 137, 195}, 
   227 -> {211, 241, 243}, 228 -> {4}, 229 -> {21, 36, 171}, 
   230 -> {41, 51, 270}, 231 -> {6, 106, 124, 193}, 
   232 -> {137, 144, 184}, 233 -> {39, 44, 160, 200}, 
   234 -> {53, 117, 143, 179, 202, 211, 218, 239}, 
   235 -> {62, 66, 133, 209, 240}, 236 -> {30, 67, 80, 270}, 
   237 -> {21, 125, 175, 177, 195}, 238 -> {63, 66, 73, 131, 189}, 
   239 -> {234}, 240 -> {162, 235}, 241 -> {14, 143, 200, 227}, 
   242 -> {46, 136, 265}, 243 -> {9, 141, 227}, 
   244 -> {19, 39, 146, 181, 251, 258}, 
   245 -> {27, 122, 186, 195, 266}, 
   246 -> {55, 167, 192, 203, 250, 273}, 
   247 -> {13, 109, 161, 162, 194}, 248 -> {112, 197}, 
   249 -> {177, 206, 250}, 250 -> {16, 218, 246, 249}, 
   251 -> {44, 59, 112, 177, 186, 244}, 252 -> {90}, 
   253 -> {63, 72, 165, 167, 254, 264}, 
   254 -> {77, 100, 195, 219, 253, 263}, 255 -> {43, 144, 194}, 
   256 -> {11, 38, 141, 147}, 257 -> {87, 89, 110}, 
   258 -> {52, 218, 244}, 259 -> {136}, 260 -> {101}, 
   261 -> {12, 160, 212}, 262 -> {32, 59, 72, 127, 265}, 263 -> {254},
    264 -> {14, 117, 253}, 265 -> {37, 50, 242, 262}, 
   266 -> {128, 245}, 267 -> {32, 111, 120}, 
   268 -> {45, 49, 69, 80, 86, 130, 149, 189}, 269 -> {92, 148, 151}, 
   270 -> {230, 236}, 271 -> {47, 91, 110, 136}, 
   272 -> {38, 45, 193, 273}, 273 -> {18, 67, 127, 246, 272}, 
   274 -> {47, 83, 170, 193}};

rules = (feebee[#] & /@ rules) // Flatten;

g = Graph[rules, VertexShapeFunction -> {"Circle"}];
Show[g]

Count[ConnectedGraphQ[VertexDelete[g, #]] & /@ (VertexList[g] // Sort), False]

Nice brute force approach and thanks for posting it here. :)

Let me clear up a few misconceptions you have: The original graph was not connected. When you ran g = Graph[rules, VertexShapeFunction -> {"Circle"}]; , you removed the vertices without the edges. What you should have run was g = Graph[Range[274], rules];

Count[ConnectedGraphQ[VertexDelete[g, #]] & /@ (VertexList[g] // Sort), False] is not what we meant by a Vulnerable City, although you are close. Because the only components other than the large network were the isolated vertices, you got away with this.

Here is the foolproof Mathematica code:

In[5]:= g = Graph[Range[274], rules];

In[8]:= Select[
 Range[274], (ConnectedComponents[VertexDelete[g, #]] // 
     Length) > (ConnectedComponents[g] // Length) &]

Out[8]= {4, 18, 22, 39, 48, 59, 61, 82, 90, 101, 108, 115, 122, 125, \
126, 136, 139, 152, 165, 187, 213, 216, 225, 229, 231, 234, 247, 254}

In[9]:= Length[{4, 18, 22, 39, 48, 59, 61, 82, 90, 101, 108, 115, 122,
   125, 126, 136, 139, 152, 165, 187, 213, 216, 225, 229, 231, 234, 
  247, 254}]

Out[9]= 28

Agnishom Chattopadhyay - 4 years, 10 months ago

Hi Agnishom;

Had I even noticed those vertices without edges, I would have removed them. But you are correct, the original graph is not connected.

A few misconceptions? Ah ha, I got ya! I have thousands of misconceptions. As you well know, I am not good with Mathematica. Coupled with my inexperience with graphs (second graph theory problem I ever worked on ) we now see why I produced kaboobly doo. Yep,I got lucky, again, it is the secret I do not tell anyone.

Thank you for the code, I will need to study it for a couple of years.

bobbym none - 4 years, 10 months ago

Abdelhamid Saadi
Dec 20, 2016

This solution is based on this idea:

We remove one city $a$ from the graph.

if the cities previously connected to $a$ are not in the same component , this is a vulnerable city.

"Attack Cities and Conquer"

def initgraph():
    f = open('network-attack.txt')
    content = f.read().replace('->{',':[').replace('},','],').replace('}}',']}')
    f.close()
    return eval(content)

def component(g, x):
    res = set([x])
    a , b= 0, len(res)
    while a != b:
        news = set()
        for y in res:
            for z in g[y]:
                news.add(z)
        res = res.union(news)
        a , b = b,len(res)
    return res


def solve():
    g= initgraph()
    res = 0
    for a in g:
        sa = g[a]
        if len(sa) > 1:
            g[a] = []
            for b in sa:
                g[b].remove(a)
            c = sa[0]
            if  not all(b in component(g,c) for b in sa[1:]):
                res += 1
            g[a]=sa
            for b in sa:
                g[b].append(a)
    return res

print(solve())

Attack Cities and Conquer

Image Credit: Wikimedia Zyqqh .

The answer is 28.

3 solutions

0 pending reports