You can start by being given a starting map. It has inputs = I; outputs = O; empty elements = E. For inputs and outputs you can unambiguously say where their boundaries are. For example, between two inputs there can be no boundary, between an input and an output there must be a boundary, etc. So it is worth starting with this logic, marking all possible initial boundaries.
After this work is done you need to make an assumption about the empty element E, it can be either an input or an output. So, making an assumption for each E, you need to find the maximum number of elements that can be outputs when the line around all inputs will be closed.
Regarding the question about Kruskal's algorithm. I haven't used it. However, you will need to do checks in the process that you can get from an arbitrary entry point to any other entry point. Perhaps you can come up with an implementation using the algorithm you mentioned).
I hope this helps you get your act together and solve the problem.