Minimum Link Reallocation to Connect Repositories

Requirements

• Input:
  • link_nodes: the total number of repositories, labeled from 1 through link_nodes.
  • link_from[]: the first endpoint for each current undirected link.
  • link_to[]: the second endpoint for each current undirected link.
• Reassignment operation: remove one current link, then create a link between any chosen pair of repositories.
• Output: return the smallest number of reassignment operations needed so every repository belongs to a single connected component.
• When the total number of links is below link_nodes - 1, return -1.

Examples

link_nodes = 4
link_from = [1, 2, 1]
link_to = [2, 3, 3]
Output: 1

Repositories {1,2,3} form one component while {4} is isolated; a cycle link can be moved to connect repository 4.

link_nodes = 5
link_from = [1, 3]
link_to = [2, 4]
Output: -1

Only two links are available, which is less than 5 - 1.