Problem 4: Beehives

https://open.kattis.com/problems/beehives2

The goal of this problem is to find the smallest group of hives such that you can reach any hive within the group from any other one, even in the case that one of the paths becomes obstructed. To satisfy the first condition, we know we need the hives to be connected. To satisfy the second, we know we need a set of nodes such that there are at least two paths from every node to every other node in that set, so that if one goes out every node is still reachable. In other words, we want to find the smallest cycle!

We already know that we can find the shortest path from one node to another using BFS. We use this to our advantage to find the smallest cycle.

Key Idea:

Let’s say you run BFS from some node s. You keep track of the length of the shortest path (the distance) from s to each node you visit, along with each node’s parent. If you are now at some node v, and you find that v has a neighbour, u, that you have already visited, and u is not the parent of v, then you have probably just found a cycle!

I will more clearly define “probably”: you have either found a cycle containing s of length len = dist[u] + dist[v] + 1 (the lengths from s up to that point and the edge between them), or you know that there is cycle of length < len not containing s elsewhere in the graph. (To see the latter case in action, try running BFS starting at 0 in the first test case!) Conveniently, in both of these situations the next step is the same: BFS from every other node to see if there exists a smaller cycle that does not contain s. The smallest of all of these is, of course, the smallest cycle in the graph.

In Summary:

For every node, use BFS to find the shortest cycle containing that node. The minimum overall cycle length will be the minimum of these.

Implementation Tips:

• Keep track of the parent of each node, and the distance from each node to s.

• To keep track of the minimum length cycle in a given graph, whenever you find a cycle, set the minimum length to be = min(minimum_length, dist[u] + dist[v] + 1)