Problem 1: Reachable Roads

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

Our goal is to find the minimum number of roads that can be added to the grid so that every node is reachable. A good place to start, then, is figuring out what would make a node unreachable.

Let's say we have some node A, and we want to get to some node B. We could get from A to B if there exists a set of edges (A, e1), (e1, e2), ..., (en, B) - a path - from A to B. If such a path does not exist, A and B are unreachable from each other by definition.

We can also note that, if A and B are unreachable from each other, any place that is reachable by A cannot also be reachable by B, because then you would be able to reach B through A by travelling through that point. All of this to say, if A and B are unreachable, they must be in separate connected components. Further, as soon as we connect a node in one connected component to a node in another, all points in those components become mutually reachable.

So! To make all nodes reachable from every other node, you would need to add enough roads to connect all connected components.

If cc = # of connected components, the answer is cc-1.

How do I find Connected Components?

Use your favorite graph traversal method!

Start from some node, and if there are still unvisited nodes when your B/DFS terminates, there are still connected components for you to explore, so call B/DFS again (on an unvisited node).