Description

Advanced Cave Megapolis (ACM) is a city that survives in the underground caves after the global nuclear war. The caves are connected by passages and the whole city map can be represented by a graph with caves being vertices and passages between them being nodes.

There is a revolution in the cave city. The whole population of the city is evenly split into k parties that cannot agree on the common laws that they should adopt. They had decided to split their city into k districts and have each district’s citizens impose the laws of their liking upon themselves.

You are given a city map in the form of the graph and your task is to write a program that partitions this graph into k equally sized districts. Each district must form a connected subgraph that is represented by the subset of the graph’s vertices.

Fortunately, the number of vertices in the graph is divisible by k and the graph representing the city happens to be a cactus — a connected undirected graph in which every edge belongs to at most one simple cycle. Intuitively, cactus is a generalization of a tree where some cycles are allowed.

The example of a city map with 15 caves and its partitioning into 3 districts is shown on the picture below.

统计

递交统计

Cactus Revolution

信息

还没有账户？

登录